OILS / mycpp / datalog / dataflow.dl View on Github | oilshell.org

60 lines, 48 significant
1.once
2
3.include "control-flow.dl"
4
5// Facts and Relations (Inputs)
6// ============================
7
8// Statements can define and use variables.
9.type Reference = Variable { v: symbol }
10 | Member { v: symbol, m: symbol }
11
12// Variable (or object) `r` is allocated, or assigned a literal value, in
13// statement `s` of `f`.
14.decl define(f:Function, s:Statement, r:Reference)
15.input define
16
17// Variable (or object) `b` is assigned to another variable `a` in statement `s`
18// of `f`.
19.decl assign(f:Function, s:Statement, a:Reference, b:Reference)
20.input assign
21
22// `a` (defined at statement `sf` in `f`) is aliased by `b` in statement `sg` in
23// `g`.
24.decl alias(f:Function, sf:Statement, a:Reference, g:Function, sg:Statement, b:Reference)
25.output alias
26
27// Rules and Outputs
28// =================
29
30// `r` is implicitly defined when it is assigned to.
31define(f, s, r) :- assign(f, s, r, _).
32
33// Simple aliasing with locals.
34// a = ...
35// b = a
36alias(f, s1, $Variable(v), f, s2, $Variable(v2)) :-
37 define(f, s1, $Variable(v)),
38 assign(f, s2, $Variable(v2), $Variable(v)),
39 CFGraph.reachable(f, s1, f, s2).
40
41// Objects can be aliased too. Note the special function name and statement
42// number.
43// a.b = ...
44// c = a.b
45alias("<heap>", -1, $Member(c, m), f, s2, r) :-
46 assign(_, _, $Member(c, m), _),
47 assign(f, s2, r, $Member(c, m)).
48
49// Object members can also be aliased by locals.
50// a = ...
51// b.c = a
52alias(f, s1, $Variable(v), "<heap>", -1, $Member(c, m)) :-
53 define(f, s1, $Variable(v)),
54 assign(f, s2, $Member(c, m), $Variable(v)),
55 CFGraph.reachable(f, s1, f, s2).
56
57// Inductive case.
58alias(f, s1, r, h, s2, r3) :-
59 alias(f, s1, r, g, _, r2),
60 alias(g, _, r2, h, s2, r3).