slavapestov/factor — pull request #1121 by bjourne (2014-08-14 21:31:52+00:00)
Title: Vacant dfa

This pr adds a compiler pass intended to better record all stack manipulations to make the gc trace roots outside the stack.

First I tried extended the uninitialized pass, but it didn't work because 1) it skips over kill-blocks for some reason 2) it's logic is too simple and it doesn't track negative stack locations. So I made a new pass called vacant instead. @erg I saw your new initialized.factor pass in the initialized-fix branch but I dont think the stack tracking is exact enough.

So here is how the vacant algorithm works:

1. Initially the stack has height 0 and an empty set of replaces `0 { }`
2. If any stack location is assigned to, record that in the set of replaces.
3. If the stack height is increased or decreased, add or subtract the same amount on the replaces.
4. The stack locations to scrub are then from 0 to the height of the stack - 1 except those who has previously been assigned.
5. The overinitialized locations (the ones that needs to be recorded to fix #1021) are all negative replaces.

E.g:

initally -> 0 { }
##inc-d 3 -> 3 { }
##replace D 0 -> 3 { 0 }
##allot -> (D 1 and D 2 needs to be scrubbed!)
##inc-d -3 -> 0 { -3 } (location now outside the stack)
##allot -> (D -3 need to be traced!)

The code currently only outputs scrubbing info to the gc-maps because the infrastructure needed to trace locations above the stack isn't there yet.