| 1 | .once
|
| 2 |
|
| 3 | .include "control-flow.dl"
|
| 4 | .include "call-graph.dl"
|
| 5 |
|
| 6 | // Types
|
| 7 | // =====
|
| 8 |
|
| 9 | // Objects can be refered to by either local variables or object members.
|
| 10 | .type Reference = LocalVariable { f: Function, v: symbol }
|
| 11 | | ObjectMember { o: symbol, m: symbol }
|
| 12 |
|
| 13 | .type Value = HeapObject { h: symbol } | Ref { r: Reference } | Empty {}
|
| 14 |
|
| 15 | // Facts and Relations
|
| 16 | // ===================
|
| 17 | // The facts and relations below use live variable analysis to determine when
|
| 18 | // variables need stack roots. See
|
| 19 | // https://en.wikipedia.org/wiki/Live-variable_analysis for more details.
|
| 20 | //
|
| 21 | // A variable is considered *live* at given statement if it might be used by a
|
| 22 | // future statement.
|
| 23 |
|
| 24 | // `f` assigns `v` is assigned to `r` in statement `s`.
|
| 25 | .decl assign(f:Function, s:Statement, r:Reference, v:Value)
|
| 26 | .input assign
|
| 27 |
|
| 28 | // `f` uses `r` in statement `s`.
|
| 29 | .decl use(f:Function, s:Statement, r:Reference)
|
| 30 | .input use
|
| 31 |
|
| 32 | // `caller` binds `r` to positional argument `arg_pos` of `callee` in statement `s`.
|
| 33 | .decl bind(caller:Function, s:Statement, r:Reference, callee:Function, arg_pos:number)
|
| 34 | .input bind
|
| 35 |
|
| 36 | // The set of variables considered live on the way in to a statement.
|
| 37 | .decl live_vars_in(f:Function, s:Statement, r:Reference)
|
| 38 |
|
| 39 | // The set of variables considered live on the way out of a statement.
|
| 40 | .decl live_vars_out(f:Function, s:Statement, r:Reference)
|
| 41 |
|
| 42 | // The set of references that a function should generate stack roots for.
|
| 43 | .decl stack_root_vars(f:Function, r: Reference)
|
| 44 | .output stack_root_vars(IO=file, filename="stack_root_vars.tsv", delimeter="\t")
|
| 45 |
|
| 46 | // Rules
|
| 47 | // =====
|
| 48 |
|
| 49 | // See the definition of the GEN set at https://en.wikipedia.org/wiki/Live-variable_analysis
|
| 50 | live_vars_in(f, s, r) :- use(f, s, r).
|
| 51 | // See the definition of the KILL set at https://en.wikipedia.org/wiki/Live-variable_analysis
|
| 52 | live_vars_in(f, s, r) :- !assign(f, s, r, _), live_vars_out(f, s, r).
|
| 53 |
|
| 54 | // The set of live variables leaving a statement is the union of the inbound
|
| 55 | // live variables of the statements sucessors in the control flow graph.
|
| 56 | live_vars_out(f, s1, r) :- cf_edge(f, s1, s2), live_vars_in(f, s2, r).
|
| 57 |
|
| 58 | // All variables considered live after a statement that, directly or indirectly,
|
| 59 | // invokes the GC must be rooted.
|
| 60 | stack_root_vars(f, r) :- call(f, s, g), might_collect(g, _), !bind(f, s, r, g, _), live_vars_out(f, s, r).
|
| 61 |
|
| 62 | // If a function invokes the GC, directly or indirectly, all of its heap-managed
|
| 63 | // arguments must be rooted.
|
| 64 | stack_root_vars(f, $LocalVariable(f, v)) :- might_collect(f, _), assign(f, 0, $LocalVariable(f, v), $Empty()).
|
| 65 |
|
| 66 | // All members of context managers must be rooted.
|
| 67 | stack_root_vars(f, $ObjectMember("self", m)) :- match(".*ctx_.*__init__", f), assign(f, _, $ObjectMember("self", m), _).
|