@Andrew_Trick that was a fantastic reply. Thank you.
First, we do need some clear motivating examples to discuss.
Good idea.
But it isn't clear which ones are solved by the current PR:
Well... none of them. This only implements the flag, it doesn't add a pass to mark references unique, or update any existing passes to use that information.
To clear up which PRs/commits do what:
This is an old (and closed) PR that promoted stack-allocated references to have static access enforcement and "stack" memory kind. But, it shows some possible performance improvements that would be nice to have if we can achieve them in other ways.
This PR adds the "unique" flag to alloc_ref. That's it.
The next PR just shows a benchmark of what happens when we remove access markers in the middle of the pass pipeline. It has the same improvements as the first PR but with some added regressions... curious. I think DSE/RLE is the reason for the improvement when accesses are removed. I'm not sure why the first PR doesn't have the regressions.
And last, here's the most recent PR I created. This PR will give us a benchmark of some baseline improvements we will (hopefully) get by incorporating the "unique" information into various access optimization passes. The goal of the PR is to get a benchmark, not to commit anything. So there's a lot going on.
I suspect there are some decent motivating examples, so assuming you can uncover those
Yes, I can work to uncover these. The above PR will hopefully show the performance improvements from updating AccessedStorage::isUniquelyIdentified. I suspect we could get even better results with a custom pass, though. As you said, there are also other improvements here beyond performance. I.e., static access errors instead or runtime errors.
Structural SIL properties should be computed on-the-fly if possible as long as that doesn't increase algorithmic complexity. For example, if discovering a property only requires walking the use-def chain without handling phis, then that should always be done on-the-fly. The proposed "unique" property requires analyzing all uses if the alloc_ref. That certainly could be done on the fly, but I have to admit, caching this in a flag will be cheaper, and I do want identifying AccessStorage to be as cheap as possible--it's already used within quadratic algorithms.
To be sure a reference is actually unique, I think we have to use a quadratic algorithm, we have to evaluate every use and every use of that use and so on and so forth. So, I think the performance issue is actually quite an important one to keep in mind.
Another thing that is really neat about this implementation is that because it doesn't rely on any analysis utils, it can run in the SILVerifier. This means it can run after every pass which makes debugging extremely easy.
The flag is low-maintenance.
Additionally, if we wanted to remove it for some reason, I don't think there would be much cost to simply "turning it off."
After thinking about this more, there's another place that could have huge performance benefits from this feature. As you mentioned, the CoW "problem" discussed in:
could potentially be resolved using this flag.
Yesterday and today I spent a bit of time playing around with the example in that post to try to figure out if I could use this flag to resolve the issue. I was actually able to get rid of all the copies with:
and manual inlining. But, I suspect more complicated examples of the problem that aren't able to be optimized away could be solved by using this flag to essentially say, "if the source argument is unique, don't make a copy here." We might have to have a way to expose this on the language level, though, and that may not be the best. Especially considering that ownership changes (move only types, etc.) are (hopefully) just around the corner.