The previous algorithm was doing an iterative forward data flow analysis
followed by a reverse data flow analysis. I suspect the history here is that
it was a reverse analysis, and that didn't really work for infinite loops,
and so complexity accumulated.
The new algorithm is quite straightforward and relies on the allocations
being properly jointly post-dominated, just not nested. We simply walk
forward through the blocks in consistent-with-dominance order, maintaining
the stack of active allocations and deferring deallocations that are
improperly nested until we deallocate the allocations above it. The only
real subtlety is that we have to delay walking into dead-end regions until
we've seen all of the edges into them, so that we can know whether we have
a coherent stack state in them. If the state is incoherent, we need to
remove any deallocations of previous allocations because we cannot talk
correctly about what's on top of the stack.
The reason I'm doing this, besides it just being a simpler and hopefully
faster algorithm, is that modeling some of the uses of the async stack
allocator properly requires builtins that cannot just be semantically
reordered. That should be somewhat easier to handle with the new approach,
although really (1) we should not have runtime functions that need this and
(2) we're going to need a conservatively-correct solution that's different
from this anyway because hoisting allocations is *also* limited in its own
way.
I've attached a rather pedantic proof of the correctness of the algorithm.
The thing that concerns me most about the rewritten pass is that it isn't
actually validating joint post-dominance on input, so if you give it bad
input, it might be a little mystifying to debug the verifier failures.
With a focus on updating the documentation of Ownership SSA.
The main changes are:
* Created a new directory `docs/SIL` and moved all SIL-related files into this directory.
* Converted `rst` files to markdown.
* Extracted sections from `SIL.md` which go into very much detail - including the instruction reference - into separate files: `Types.md`, `Ownership.md`, `FunctionAttributes.md`, `Instructions.md`. Those files are referenced from `SIL.md` at the relevant places.
* Rewrote and updated the OSSA part in `SIL.md`
* Removed a few sections, which are not relevant anymore, like "Value dependency" (which is replaced by ownership concepts).
* Fixed and improved a lot of small things.
