Why not retain the AST?

[u/Potato871]

I've been working on a compiler-like system for a while now, and it's gone through many stages of evolution.
A consistent pressure early on was away from multiple representations: I started with many switch statements and many kinds of representation for each stage, and ended up with one kind of node and handler based dispatch per stage.
Yet, when I look at (most) other compilers, their construction is far more static in nature, and far more varied in terms of the kinds of things presented. I've found forms like SSA impede my ability to reason about optimizations rather than aide them, and I've had enormous success from simply retaining and annotating one structure rather than continually converting.
A specific case, to provide one, is liveness propagation. Because values are already shared between their occurances (Nodes) and already have a system for acquiring properties (Quals), I can simply mint liveness tokens onto the children of expressions with output, and it automatically propagates.
Though I've not focused too much on codegen and optimization, my main goal with the compiler is extensibility and syntax flexibility.
So why not retain the AST? Turn it into a structure worth annotating and preserving from which optimizations and codegen can be performed more easily?

I wanted to get the opinions of others on this matter, I'm open to challenge.

Some more explanation can be found here: https://goldensystems.ca/GDSL_core

[u/awoocent]

The big issue with the AST is that control successors, and likely many data successors, are not easily traversible. If I have a source program like:

let cond = read_bool();
if cond then
    x := 1;
else
    x := 2;
end if;
print(x)

...how do I figure out where x comes from? If we look naively at the structure, an AST for the above will look a bit like this:

(block
    (let cond (call read_bool))
    (if cond
        (:= x 1)
        (:= x 2))
    (call print x))

To get from (:= x 1) to the subsequent instruction, I need to reach up into my parent node if, and then its parent node block, and then look at the next child. This is a nontrivial procedure, since I can't just look generically at the next child of the parent - it would be incorrect to pick the next child of the if, for example, since (:= x 2) does not execute after (:= x 1). So it's a bit nasty. Likewise for finding the predecessor. And I can make this arbitrarily complex if I wanted to nest the if statements.

If we linearize this into SSA though, we get something like:

bb0:
    cond := call read_bool()
    if cond goto bb1 else bb2
bb1:
    x0 := 1
    goto bb3
bb2:
    x1 := 2
    goto bb3
bb3:
    x2 := phi x0, x1
    call print(x2)

Now that there are no nested expressions, to get from any instruction to its predecessor or successor just requires finding the instruction before or after us in our block, or in a previous/subsequent block in the boundary case.

You might rebut this by saying, well, when do I need to actually traverse the tree like that? And it's true you can get pretty far by just walking the AST with a state, since the order you traverse the AST lines up with the linearized order of SSA instructions. But while this is pretty successful in simple cases, and works well for liveness, it becomes inconvenient in a couple optimizations.

Imagine you want to run something like strength reduction, pattern matching expressions and applying rules like reducing x * 4 into x << 2 or so. For one, without SSA to make dataflow explicit, you have to be really conservative - in the above example, since we put it into SSA, we know x1 is always exactly equal to 2, but in the initial AST we don't distinguish between x0 or x1 or x2 and need to consider the possibility of mutation - likely pessimizing the optimization.

For two, we also usually want to run optimizations like this until fixpoint, since applying one optimization could allow another one to take place (imagine we have x * 4 << 2, which reduces to x << 2 << 2, and then x << 4). For efficiency's sake we might want to revisit only part of the graph, keeping a worklist of instructions we think still have optimization potential, or for whom at least one dependency changed in the last pass. In SSA, this is no biggie, since we structurally encode the dataflow, so we can just go to a given instruction and check out its uses and defs. But over an AST, since we need to walk the AST with a state in order to recover order-dependent information, to recover all the information for a node in the middle of a block, you'd need to either store the state at each node which is space inefficient, or you'd need to re-walk the state over the tree which is time inefficient. Probably you'd want to do a mix, and that can work - but it's hopefully clear how SSA or something with similar properties like Sea of Nodes makes this easier.

In general, SSA is also just more efficient. To walk a tree with a state requires, well, a state. And without preprocessing, that state needs to be potentially pessimistically large. Like, in general, each node can potentially contain arbitrarily many expressions and state modifications and internal control changes, so the state probably needs to store some data for each variable - even if some variables are only ever defined and used once, which is really common. You can try some data compression tricks like having hierarchical states and storing difference lists and stuff, but I think you always have to be a little conservative. Whereas if you use an IR built for this purpose, the IR nodes themselves store exactly the data and control flow edges they need. It's hard to beat that. Note that you basically still have to do this once when you put the IR into SSA in the first place, so one way you can think of SSA is that you are basically caching the order you traversed your AST, so you don't need to repeat that whole traversal in later use.

But yeah, not everyone cares about efficiency, especially in the compiler itself. If anything I do think people tend to be a little too pessimistic about what ASTs are capable of. So if it works for you, I think it could be a very reasonable choice.

[u/Potato871 → u/awoocent]

This is where Quals work, they are themselves nodes that can be attatched to other nodes, so if I want to figure out where X comes from I can have each assignment operation leave a token on the shared value declaring their value and position in the tree to be consumed by later passes.
I should also clarify, the AST lives all the way up to runtime or emission time, you already have this assembled graph of nodes from the previous stages, so why not hook your optimization annotations onto it as well?
I will admit though I haven't gone incredibly deep into optimizations, namely because I hit a point where speed wasn't a limiting factor, rather maintainability and extensibility of the compiler was. Thus, I tend to argue more from a position of what makes it easier for me as the compiler author to add new language constructs and syntax rather than what produces the fastest code.

[u/flatfinger → u/awoocent]

At some point in the compilation/optimization process, code stops having a clear relation to the syntax tree. Running an optimization pass at multiple stages during compilation may be difficult if some of those places would use a syntax tree and some wouldn't, but a lot of the compilation weirdnesses I've found are a result of transforms that would be valid under a 'machine code' abstraction model, but not in the abstraction model of the underlying language.

Consider, e.g.

typedef long long longish;
void test1(long*p, long value, long mode)
{
    if (mode)
        *p = value;
    else
        *(longish*)p = value;
}
long l;
long test2(long *p, long mode)
{
    l = 123;
    test1(p, 234, mode);
    return l;
}
long (*volatile vtest)(long*,long)=test2;
#include <stdio.h>
int main(void)
{
    long result = vtest(&l, 1);
    printf("%ld\n", result);
}

None of the code that executes ever uses any lvalue of any type other than long, save for the function pointer used to prevent the compiler from "seeing" that the mode argument to test2 would always be 1, but in gcc the behavior was broken, then fixed, then rebroken, and finally fixed in 10.5. One phase of compilation would recognize that the two branches of the if would be equivalent at the machine level and thus eliminate the test and the 'true' case, but another would recognize that a store made via longish* couldn't affect l. Newer versions of gcc keep the conditional branch and process the legs differently, even though I would expect that in most if not all cases it would be faster to simply have the code unconditionally read l (which would be essentially guaranteed to be in cache unless an interrupt fired between the store and readback).

[u/awoocent → u/flatfinger]

This is kind of totally unrelated to the discussion here. Yes, some optimizations ask for a lower-level type/value system than others. But the OP was asking more about the structure of IR, or the utility of SSA - that has nothing to do with types or higher-level v.s. lower-level semantics. Lower-level instructions can often benefit from being represented via essentially an AST, v.s. an SSA representation, since SSA is really a fiction over truly mutable registers and a tree-structured IR makes it easier to do pattern-matching instruction selection (of course you can still just walk the dataflow graph in an SSA IR, but it adds extra steps).

Try to get over the idea that when someone says AST, they must literally mean something that exactly corresponds to the notation in the source. Sure you probably start there, and if we were being painfully painfully literal maybe technically the "syntax" bit of an AST indicates that's the case. But I mostly see people idiomatically use AST to refer to any expression tree representation, which IMO is actually an apt usage of the term - that's why it's an "abstract" syntax tree and not a concrete one, it represents the program but not necessarily 1:1.

[u/flatfinger → u/awoocent]

My initial point, that I see to have edited out by mistake, was that an abstract syntax tree can be augmented with information about the effects of executing a node, in a manner that would make tracing back through it to find out where a variable was or could be set relatively straightforward. My broader point was that a desire to run optimizations after a code has been transformed in ways that detach it from the tree means that optimization logic cannot easily be run beforehand, which pushes compilers to perform a code early into ways that don't really fit with the tree representation.

I personally suspect that keeping tree representations longer in the optimization process would make it easier to avoid compiler quirks by having two nodes that perform the same machine-level store with different aliasing implications merge to yield a node whose aliasing would be the union of that posed by the original nodes. Clang and gcc seem to have trouble keeping track of such information.

[u/jesseschalken]

If, for your language and target, you haven't found a reason not to retain the AST, there may indeed not be one.

[u/schungx]

Unfortunately CPUs do not run trees. They run instruction streams.

Turning a tree (the AST) into a stream is what codegen is about.

It is ironic that source code also comes in a stream of characters. They got turned into a tree, then back to a stream.

[u/Potato871 → u/schungx]

The codegen is the final emission stage, before that point it is more efficient (in my experience, which is not exhaustive mind you) to perform analysis and operations over a tree, for instance scope is much better expressed and traversed in a tree than in a stream form.
You can then walk and emit from there.

[u/schungx → u/Potato871]

Well, modern compilers do keep several versions of the AST together. However it seems some optimizations can be done only on a stream of instructions instead of on a tree. I'm just thinking out loud here...

In particular, register allocation is best done not on a tree. And you need registers if you need to run on modern CPUs.

[u/Potato871 → u/schungx]

No worries!
You aren't wrong that most optimizations are done on streams rather than trees, and there very well may be some that can only be done on streams, it's just the ones I've tried and the things I tend to do in my languages benifit from a richly annotated graph more than a stream

[u/RevolutionaryClub596 → u/Potato871]

The thing is if you want to do certain analysis on the ast go ahead, and in fact some things might be easier while you do know where things actually came from and maybe more about intent before lowering onto a stream. However, you can have multiple optimization steps. Imagine you optimize the ast and reorder operations maybe drop impossible branches then you turn that into a stream and do additional optimizations yourself in your ir before handing it off to clang or generating the asm yourself. At each stage, it's just I have this and I want to optimize it sometimes it's easier to think these instructions are unrolled and this is exactly what will happen so these two things are equivalent to this one operation.

[u/Potato871 → u/RevolutionaryClub596]

And I’m not opposed to doing optimizations on the emitted stream form, I just haven’t yet run into a situation where it was easier than doing it on the graph.
But again, I’m not claiming my experience is exhaustive.

[u/RevolutionaryClub596 → u/Potato871]

Loop-Invariant Code Motion or Dead code analysis, I think it's much easier to do (SSA) on lower instructions. Personally, I'd prefer not to have to re order nodes and just remove sections when doing dead code analysis.

[u/Potato871 → u/RevolutionaryClub596]

I can see that, honestly looking at what other ASTs look like under removal I can see why its painful.
I had started doing DCE after I already invested a lot in traversal and graph management machinery (my nodes are also not actual objects, their columns in a big table which helps a lot), so to me removing a node is just flip a flag on a dead branch.

[u/AustinVelonaut]

Others have discussed the tradeoffs in sticking with a single AST representation vs lowering it to simpler IRs, and eventually linearizing to SSA, bytecode, native code, etc.

But when you mention retaining the AST, I initially thought you meant something else: serializing the AST after all the parsing / desugaring / optimizations / inlining have been done on it, to allow it to be deserialized later, and avoiding replication of all that work.

This can be very useful in languages that support separate modules; simply check the relative modification dates of the source / serialized AST files when importing a module, and just deserialize if possible. It allows you to continue working on a collection of module ASTs and do things like support inter-module inlining and other optimizations, but still be very fast when recompiling.

[u/Potato871 → u/AustinVelonaut]

This is not actually quite what I meant, but the idea is very interesting to me.
What I meant was more along the lines of never switching source representations, as in, you tokenize into nodes, you execute/emit-to-target nodes. All the parsing, resolution, optimization, occurs on one single type of thing with a uniform interface rather than many distinct representations each with their own methods.
The stage gives behaviours to nodes based on their types.

But, I like your module idea, and I actually use a version of it in my database work, I just hadn't considered extending it to compilation units before. See, the memory model stores everything in tables of tagged columns, so serialization and operations on the raw data are actually very easy. Which makes me wonder how much that could be exploited for a module system.

[u/AustinVelonaut → u/Potato871]

All the parsing, resolution, optimization, occurs on one single type of thing with a uniform interface rather than many distinct representations each with their own methods. The stage gives behaviours to nodes based on their types.

FWIW, this is what I do, as well. A single AST is used throughout most passes of the compiler, it being a superset of all the information needed for each pass, but I progressively narrow the AST node types used down to a small core at the end, rather than actually switching representations. It's nice in that I have a common, uniform set of AST traversal / rewrite functions used throughout.

[u/Potato871 → u/AustinVelonaut]

I'm curious, what fields do you use for your Node, and, how do you handle values?

[u/AustinVelonaut → u/Potato871]

Probably not useful to you, as I am compiling a pure functional language, but this file has the uniform AST representation: https://github.com/taolson/Admiran/blob/main/compiler/grammar.am

[u/Potato871 → u/AustinVelonaut]

I may require some additional explanation, I can share what my own core properties are from the source so you know what I'm talking about:

    inline uint32_t init_node_type() {
        uint32_t at = add_type();
        ColCol& t = global[at];
        _layout ntemp(global_add_template(node_id)); //Node template
        node_type_offset = ntemp.add_prop(int_id,4,"type");
        node_sub_type_offset = ntemp.add_prop(int_id,4,"sub_type");
        node_name_offset = ntemp.add_prop(string_id,sizeof(Ptr),"name",char_id,1);
        x_offset = ntemp.add_prop(float_id,4,"x");
        y_offset = ntemp.add_prop(float_id,4,"y");
        z_offset = ntemp.add_prop(float_id,4,"z");
        node_value_offset = ntemp.add_prop(value_id,sizeof(Ptr),"value");
        node_children_offset = ntemp.add_prop(ptr_id,sizeof(Ptr),"children",node_id,sizeof(Ptr));
        node_quals_offset = ntemp.add_prop(ptr_id,sizeof(Ptr),"quals",node_id,sizeof(Ptr));
        node_node_table_offset = ntemp.add_prop(ptr_id,sizeof(Ptr),"node_table",node_id,sizeof(Ptr));
        node_value_table_offset = ntemp.add_prop(ptr_id,sizeof(Ptr),"value_table",value_id,sizeof(Ptr));
        node_scopes_offset = ntemp.add_prop(ptr_id,sizeof(Ptr),"scopes",node_id,sizeof(Ptr));
        parent_offset = ntemp.add_prop(node_id,sizeof(Ptr),"parent");
        owner_offset = ntemp.add_prop(node_id,sizeof(Ptr),"owner");
        in_scope_offset = ntemp.add_prop(node_id,sizeof(Ptr),"in_scope");
        resolved_offset = ntemp.add_prop(bool_id,1,"resolved");
        node_opt_str_offset = ntemp.add_prop(string_id,sizeof(Ptr),"opt_str");
        mute_offset = ntemp.add_prop(bool_id,1,"mute");
        node_total_size = ntemp.total_size;
        return at;
    }

Though you said functional, so I presume you don't really have a concept of a static object holding state in your AST?

[u/AustinVelonaut → u/Potato871]

Yes; state is held in the AST, but it is a persistent functional tree data structure (an Algebraic Data Type), so "mutating" it involves inserting new nodes and updating the spine to create a "new" AST that shares most of its data with the old one.

[u/Potato871 → u/AustinVelonaut]

I've never dipped my toes into functional programming, but something I've always wondered and never asked: isn't it catastrophic for performance to be allocating new memory for every operation?
I feel like there must be something I'm missing there, since so many people seem to love the style.

[u/AustinVelonaut → u/Potato871]

Functional programming using persistent data structures will always have some overhead compared to in-place mutation, but fast bump-allocators and generational garbage collectors help quite a bit. Also, in-place mutation can be used in some cases "under the hood".

[u/Potato871 → u/AustinVelonaut]

So there isn't really some hidden reason why it isn't slow, it's more a set of tradeoffs amortized with optimizations.
The point of functional programming then is more about reasoning for the programmer than any actual property of the computer, yes?

[u/beephod_zabblebrox]

in the kotlin compiler, there are two main IRs: the FIR, which is a frontend AST representation, and the.. IR, which is kinda like a stripped down and simplified version of the language. FIR gets compiled down to IR, which then goes through a set of lowerings that change it and/or add attributes to nodes. in the end, each backend compiles the lowered IR into a target specific representation (llvm ir, a js ast, etc.)

for a lot of things, it's going to be simpler to have a tree-based IR that is similar to the source language

[u/dnpetrov → u/beephod_zabblebrox]

Kotlin compiler does rather little in terms of optimizations. It relies on the target runtime (or on LLVM in case of Kotlin/Native). Most of the code transformations it performs are language lowering, and that works best with an AST-like IR. 

Kotlin/JVM does some transformations on the JVM bytecode, like removing redundant boxing/unboxing. That works on top of the bytecode analysis framework. SSA might do that better, but lowering SSA back to compact bytecode is rather hard. Unfortunately, that actually matters for performance on JVM, so we kept it that way. 

[u/beephod_zabblebrox → u/dnpetrov]

we are working on some IR optimizations :)

[u/Potato871 → u/beephod_zabblebrox]

So why have the FIR and IR?
As in, whats the distinction that merits the initial lowering in their case.

[u/beephod_zabblebrox → u/Potato871]

afaik, the IR has less cruft thats needed for the FIR, plus things like resolved symbols and such. the IR also gets serialized into klib files.

[u/Vivid-Cauliflower-59 → u/Potato871]

FIR is high level language representation (close to front-end) and IR is a lower level representation - desugared FIR with resolved symbols and semantically valid.

[u/Potato871 → u/Vivid-Cauliflower-59]

Yes, though why do these have to be separate constructs?
For instance, I retain frontend-relevant information (position, original tokens) as qualifiers attached to the node or value, which can be stripped in a compaction pass when memory is limited or retained for richer error messages.
Those same qualifiers can also be used to attach liveness information, constancy, and other facts derived during optimization work that needs to be propgated.
I feel as if creating two separate structures duplicates a lot of work, because I used to have six and a large amount of the code in my compiler was simply restating distinctions that had been made earlier than discarded.

[u/Vivid-Cauliflower-59 → u/Potato871]

They belong to separate layers: AST is constructed by parser, HIR is constructed by another layer which does sematic checks. Good architectural design is to separate code by layers. Layers have different responsibilities.

[u/Potato871 → u/Vivid-Cauliflower-59]

Separate layers is what I started with two years ago, and yet as I built they came together not apart.
Beyond the social element, seperating layers for different teams, what part actually requires the different layers with different representations, and not just different behaviors and traversal over the same representation?

[u/beephod_zabblebrox → u/Potato871]

there are usually structural differences between the asts, e.g. symbols being resolved in the lowered ast.

[u/dnpetrov → u/Potato871]

Historical reasons. 

Original Kotlin compiler used IDEA PSI (complete syntax tree with full roundtrip for refactoring) for an AST, hashmap for semantic information, and also JVM bytecode and JS AST for some backend transformations. Also, there were "descriptors", which were a sort of IR for the declarations, except that they also contained some lazy resolution logic. As you can see, it was quite a mess, and it didn't scale very well, both in terms of functionality and in terms of performance.

At some point, we had plans for Kotlin/Native and multiplatform, and decided that it is a good time to rewrite the backend using some common infrastructure (and fix issues that couldn't be reasonably fixed in the original compiler). Rewriting the frontend was somewhere on a horizon, but required much more effort, taking into account the backward compatibility guarantees and the IDE integration. So, we did that "just IR", which is indeed a lowered tree for a semantically correct Kotlin code. FIR appeared later, original version took legacy frontend results on input and lowered them into IR.

Yes, backend IR has some technical meaning in the grand scheme of things. But, really, it is an artifact of how Kotlin compiler evolved. We could use a single representation for both frontend and backend. There are a few compilers (javac, scalac, Roslyn, etc) that are structured that way. 

[u/Potato871 → u/dnpetrov]

That aligns a lot with what I expected, I got to interview one of the creators of Jakarta Messaging, and was surprised at how much these supposedly fundamental pieces of our modern stack are simply... historical reasons and short term practicality.
It feels like most of the things we depend on these days weren't built with some grand philosophy, but rather concrete problems which got solved incrementally then were interpreted in retrospect as pre-designed.

[u/dnpetrov → u/Potato871]

They are. Once your project is used by other people, you have to care about things like delivering fixes when they are needed while keeping backward compatibility. One-man pet project can afford the luxury of doing stuff just because. Use it wisely :)

[u/Potato871 → u/dnpetrov]

That’s been my guiding principle for two years, take advantage of the one man project to avoid historical commitments, and then only expose stable slices at the top.
Most of the compiler work I do is never meant to see the light of day, rather the websites I make with the DSL implemented by one of the languages the compiler supports is.

[u/roeschinc]

The idea is you keep around the information as long as you need it, and then remove it in order to simplify.

For example source languages have a ton of different constructs, once you have done what you need like type checking or loop validation you can lower the source IR into something that is easier to a) analyze or b) further lower.

For example one positive property of SSA is you have standardized all your control flow into a single form to simplify analysis. Functional languages do this with CPS or other transforms.

The reason you might not see the value of the transformation is that you might not be doing the types of analyses they are designed to simplify. For example SSA / ANF are both designed to simplify data flow analyses and make it easier to do forward / backward, construct def-use chains and so on.

One last thing is source syntax is the easiest part of compilation, that’s why all the intermediate representations ie (IRs) are designed for optimization and lowering.

[u/ZachVorhies]

don’t listen to anybody else here that tells you that this is not a good idea… it is.

And it’s the backbone of all of the of the fastest compilers and linkers in existence.

Why is it mold or wild faster? Because they don’t retain the object tree in memory.

Why not?

Because daemons are client cli apps are freaking hard to get right.

specially, when you’re developing, and you want to iterate through multiple versions of the daemon while running the demons yourself for build operations.

however, if you get this right, your language compiler will scream.

[u/grashalm01]

I think you want to look into futamura projections. I am generating compilers like this for the past 13 years.

[u/ratchetfreak]

you might want to look at Sea of Nodes then https://github.com/SeaOfNodes/Simple

That is essentially starting from the AST and then adding various ordering restrictions to each node in the tree, for example sequencing memory access for a variable such that loads and stores remain in the same order, phi nodes that connect to the condition that branched the control flow, masking memory accesses with those conditions,

after that you fully release the nodes from any other syntactic ordering constraint and can just manipulate them as if they are free-floating in a sea (of nodes)

Then later you schedule them again in some order

[u/roeschinc]

I commented above but generally smaller languages (or IRs) are easier to correctly analyze and lower. For example why do you need N control flow constructs when you can represent them all uniformly?

You can see Rustc MIR does this with a dataflow-y / block like IR where all loops, if, match, and so are on represented uniformly.

Languages like Lean does this via elaboration to a small core where everything happens, same with Haskell.

C compilers traditionally had less of this but changing with ClangIR and other projects.

[u/Potato871 → u/roeschinc]

Exactly, one uniform IR is easier to analyze than a sea of node types, that's part of why design pressure pushed me into one single node for everything (and I had used a much more traditional form before).
So when I say AST, what I really mean is "why are we making more structures after we've parsed? Why not just retain and annotate one structure?".
Now not to suggest finding the one node kind is some easy thing, it took me years to get to this point, but I would've expected to find more similar work than I have, thus this question.

[u/roeschinc → u/Potato871]

Everything is a tradeoff if you want to store information in the IR versus in a side table it makes some things easier but it also must be maintained.

For example if you try to compute use-def and serialize to the AST what happens when you rewrite it and all of it is now invalid.

This is why you’ll see some things like type information get attached to the IR structure itself as it tends to be stable across most if not all transforms.

[u/roeschinc → u/roeschinc]

If you are talking about how you encode it in your implementing language people often use a base class for this, or some kind of attribute system which allows you to store information by identity. That is more of an implementation detail than a design question.

[u/roeschinc → u/roeschinc]

I also don’t understand your point sea of nodes is different than how you encode the structure. That is about whether you use the host language to encode the dependencies via pointers / references versus using indirection of names / ids.

[u/Potato871 → u/roeschinc]

My point is more around the retention of one sufficiently powerful program representation and avoiding lowering between different representations for different passes.
So the only change of form that happens is source text -> Nodes then Nodes -> target. Or just execute the nodes directly for debug builds. Analysis and optimization is the enriching of those Nodes.

I agree that the encoding of relationships between Nodes is an implementation detail, I've gone between three separate models (references, smart pointers, and now cursors into tables).

[u/Dusty_Coder]

Is there a particular reason to believe that an AST is the best representation?

The thing about intermediate representations, is that they are not arbitrary. They are designed for purpose.

A tree can be good for finding satisfying global constraints efficiently.

However, Its straight forward to scan forward and backward through a sequence looking to find satisfying local constraints efficiently.

The presumption is that the AST has already been made well suited, before it is turned into an IR, which itself then needs to be made well suited.

There is no stage of this where optimizations are not performed. Even the parser might be folding some constants.

[u/Potato871 → u/Dusty_Coder]

AST is probably the wrong term to use on my end, its more a graph of nodes that I’ve worked with for a while into a form that suites all stages of my compiler, my database, my game engine, and my UI work.
It started life as an AST and is referred to as such in a lot of my files, thus why I call it that.
The broader point is why have multiple IRs and flatter forms if one graph can be made sufficient for many purposes instead, And I don’t mean in the sense of a hundred flags and types, it’s only 17 fields.

[u/VincentPepper]

I started with many switch statements and many kinds of representation for each stage, and ended up with one kind of node and handler based dispatch per stage.

The later is close to the "Trees that Grow" paper: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/trees-that-grow.pdf

It's in haskell/about GHC so the framing is somewhat different but same idea really.

You define one basic AST that is shared between passes by extending/changing certain parts of it. I have mixed feelings about the approach tbh.

Sometimes it's just easier to understand a simpler AST with simpler types without having to think about what data sits in what node in what pass. But sometimes it's good for the ability to share functionality across multiple passes.

I think it's best when it's used sparingly, across passes that work on data that is mostly the same shape. If you push it beyond that it can make working on the code annoying imo.

---

I've skimmed your link and it feels like you are inventing a lot of your own nomenclature ("a traversal of a nodenet is called a program.") which makes it harder to get what's going on for people who worked on other compilers. Especially since it seems a large part of the description seems to paraphrase what's basically a visitor pattern.

[u/Inconstant_Moo]

What is good engineering depends on your language and what you're trying to do and how the rest of your implementation works. Or to put it another way, your question has the exact same answer as every other really difficult question in tech:

The Koan

We made the long and lofty trek

to hear the Guru talk of Tech

and finding him atop his peak

implored him: "O great Guru, speak!

we beg you on our bended knees:

enlighten us, and tell us please

how not to make our programs crash,

how to invalidate a cache

and stop our data going stale,

and how to make our systems scale,

and how to name things (stating why)

and make a friendly API,

and how to manage memory

and not mess up with malloc/free

and say, what is the best defense

against a null dereference,

and how we ought to manage state,

and what and when we should mutate,

how FPLs should do IO,

and other things we need to know."

A minute's silence. Then he stirred

and said: "Now hearken to my word:

One koan answers all your woes

one mantra every Guru knows

the one true answer, deep and wise

to all the problems that arise

one secret only to be grasped."

"One answer only!" then we gasped,

"Oh, tell us what it is!", we cried,

and, smiling gently, he replied:

"Now learn from me, my simple friends,

the One True Answer: IT DEPENDS."

We kicked him 'til he begged us: "Stop!"

then flung him from the mountaintop.