@ChrisDodd I think this is enough as the first approximation. I converted majority of frontend passes. Few remaining ones are a bit more tricky and might require separate dedicated treatment and larger refactoring

Take home messages:

• ResolutionContext is fine for top-level passes. However, there are lots of cases where visitors are spawned on sub-trees, but have to resolve declarations globally. Then things become much more messy as we'd need to make them ResolutionContext as well, plus pass context around. This defeats the idea of memoization as their lookup caches are effectively re-created and destroyed. We need to have a way to share / pass caches around different sub-contexts.
• We likely need some centralized SymbolTable to handle all declaration names. Otherwise we'd need to walk over the whole IR tree just to collect names. And we do this quite often. In the testcase I do care about it takes ~50 ms just to collect names. And we do this more than 20 times, certainly. Sometimes only to create couple of temporaries.
• TypeInference is run everywhere. Something should be done here definitely. In my testcase a single full TypeInference run is ~700 ms.

Here are benchmarking results (10 iterations + warmup) for the downstream app:

• ResolutionContext is fine for top-level passes. However, there are lots of cases where visitors are spawned on sub-trees, but have to resolve declarations globally. Then things become much more messy as we'd need to make them ResolutionContext as well, plus pass context around. This defeats the idea of memoization as their lookup caches are effectively re-created and destroyed. We need to have a way to share / pass caches around different sub-contexts.

One major concern I have is that we never invalidate things in the ResolutionContext cache -- if this is a transform pass (or run multiple times with transforms between), it is easy for things in the cache to get out of date. We should definitely have a debug mode build where all the cache hits also do a full lookup to ensure it gets the same value back -- slow but necessary for correctness verification. If we can get the cache invalidation correct, then we could look into sharing the cache between passes. As it is currently, I'm afraid we really should be invalidating the cache every time in init_apply.

• We likely need some centralized SymbolTable to handle all declaration names. Otherwise we'd need to walk over the whole IR tree just to collect names. And we do this quite often. In the testcase I do care about it takes ~50 ms just to collect names. And we do this more than 20 times, certainly. Sometimes only to create couple of temporaries.

Yes, could have a single MinimalNameGenerator that all passes share, rather than creating new ones all over the place.

• TypeInference is run everywhere. Something should be done here definitely. In my testcase a single full TypeInference run is ~700 ms.

My next step plan after eliminating the refMap everywhere is to eliminate the typeMap too -- if you run TypeChecking with updateExpressions = true, it will copy the type of every Expression into the type field of the expression, and then you should not need the typeMap pretty much anywhere. So the typeMap just becomes a short-lived temp between TypeInference and ApplyTypesToExpressions.

In addition, all the readOnly = true runs of TypeInference/TypeChecking are unnecessary if the rest of the compiler is correct -- so you should not count them against the total run time. They only exist to trigger BUG_CHECKs if some other pass screws up the types.

One major concern I have is that we never invalidate things in the ResolutionContext cache -- if this is a transform pass (or run multiple times with transforms between), it is easy for things in the cache to get out of date

I thought about this. However, I do not think this will be a problem. IR is immutable, so if something was transformed, it will be entirely new Node. Therefore we'll have two cases:

• Lookup using "old" (untransformed) node. Fine, we'll return old declaration
• Lookup using "new" (transformed) node. We'll likely will not have it in cache, so we will resolve it again and cache the result.

So, the cache itself might have stale things, yes, but the answers will always be correct. Certainly, we might need invalidate it between passes, but I mostly concerned about nested cases where one pass applies couple of other visitors underneath. For those it would be great to inherit the cache. I put few FIXMEs in certain places and some of them are indeed require such caching, iirc – GetWrittenExpressions and ReadWrites are.

My next step plan after eliminating the refMap everywhere is to eliminate the typeMap too -- if you run TypeChecking with updateExpressions = true, it will copy the type of every Expression into the type field of the expression, and then you should not need the typeMap pretty much anywhere. So the typeMap just becomes a short-lived temp between TypeInference and ApplyTypesToExpressions.

Right. And this is actually already done in few places. However, things are written to require typeMap, uh-oh. Read-only type inference is actually not read-only as it still clones the whole program (and then just throw out everything). This type checking should be optional, right. E.g. in some "expensive checks" mode.

One major concern I have is that we never invalidate things in the ResolutionContext cache -- if this is a transform pass (or run multiple times with transforms between), it is easy for things in the cache to get out of date

I thought about this. However, I do not think this will be a problem. IR is immutable, so if something was transformed, it will be entirely new Node. Therefore we'll have two cases:

• Lookup using "old" (untransformed) node. Fine, we'll return old declaration
• Lookup using "new" (transformed) node. We'll likely will not have it in cache, so we will resolve it again and cache the result.

But the lookups (keys) are by name (cstring), not by node. So if you put a node in the cache under a name and that node is later transformed, and then after that you look up the name again, you'll get the old node, not the transformed node.

However, it does look like most of the lookups (all those that call resolve or lookup) bypass the cache -- the cache is only used for getDeclsByName. In addition, in that case it also looks up the namespace in a cache first, and that is a Node *, and any change of any declaration in the namespace will result in the creation of a new INamespace *, so that lookup won't find the old cache. But we probably need to consider this if we want to clean up all this caching stuff to make it more useful.

But we probably need to consider this if we want to clean up all this caching stuff to make it more useful.

Yes, right, caching is essentially unwrapping a namespace, so stuff is keyed by INamespace*, this was enough to drop the complexity from quadratic to linear (especially during shadowing checks). In addition – all current code is refMap-oriented. So it expects to find old (untransformed) result, but yes, I fully agree, the lookup should probably be rethought. There are also some users that expects to do some lookups outside of the current context (e.g. analyzing a call we only have context of caller, but might want to check the callee).

Yes, the goal is to get rid of reference map and switch to more fine-grained approach. Reference map is global: you recompute it for the whole program (doing separate top-down traverse). However, in many cases you'd only need couple of paths being resolved from there. So, this is a huge waste of computational resources. It is not about inspectors, but transforms as well.

I think that has its uses? Imagine an interpreter that does not modify the program but uses many different visitors to traverse it. Precomputing the refMap once is all that is needed.

Imagine an interpreter that does not modify the program but uses many different visitors to traverse it. Precomputing the refMap once is all that is needed.

And these visitors can make us of something like refMap, true. Here we are talking about the frontend (and midend, but I have not touched it yet) that changes things over and over again. Each Transform effectively kills refMap, so it had to be recomputed from scratch. Note that common Visitors in this PR take DeclarationLookup interface (e.g. MethodInstance::resolve) that is used for resolution.

In general, if you're having some global objects that are expensive to recompute, but you'd need to recompute them after any IR change, then it smells like a big problem and design flaw IMO.

ResolutionContext certainly is not perfect:

• It only does lookup within the current context (so you cannot e.g. analyze the call and do lookup in the context of the callee declaration)
• In some cases we recreate it again and again. Fortunately, this is mostly in the case of small leaf lookups, so we won't waste lots of things

And see the discussion above how the internal cache of ResolutionContext could optionally be reused / shared in the nested lookup. I would say this is something that needs to be carefully designed.

As a loud thinking: if the ResolutionContext could be shared, then in your interpreter example, it could be created by top-level pass and then passed down to all visitors. They will populate it lazily effectively building refMap under hood on-fly.