paniq

Relation-Rule Based CFG Inference

A relational event graph is described with unpredicated rules relating events, connecting a product of n sources and m conditions to a single sink (also called the goal). The format is as follows:

Y :- X[1], X[2], ..., X[n], c[1], c[2], ..., c[m].

means "when all events X[1]..X[n] have happened, and all conditions c[1]..c[m] have been met, then the goal Y will happen". Because the right hand side is a product, the arguments are commutative and associative, so that the rule makes no demands as to in what order the sources are called, or the conditions are evaluated.

The resulting graph is a directed hypergraph of the B-graph class, with each rule constituting a B-arc.

paniq

fn bitstripes (n)
    -1:u64 // ((1:u64 << n) | 1)

fn logleveld (x)
    findmsb x

fn tt->anf (x)
    w := (x == 0) 0 (logleveld x)
    S := (logleveld w) + 1
    x := fold (x) for i in (range S)

paniq

fn bitstripes (n)
    -1:u64 // ((1:u64 << n) | 1)

fn rbitstripes (n)
    d := (1:u64 << n) | 1
    f := max (n * 2) 1
    k := 64:u64 // f
    kf := k * f
    sh := 64:u64 - kf
    m := (-1:u64 // d) >> sh

paniq

Low-Level Datalog

With the right low level composition primitives, it would be possible to even describe accelerating data structures in a relational way.

Let's begin by treating the heap as a special relation.

# arcmem heap as polymorphic lattice
# .decl heap(address : T*, value : T)

paniq

% strongly connected components

% example from sedgewick, algorithms in C++, part 5, figure 19.28, §19.8, p. 207
% edge(from, to)
e(0,1). e(0,5). e(0,6).
e(2,0). e(2,3).
e(3,2). e(3,5).
e(4,2). e(4,3). e(4,11).
e(5,4).
e(6,4). e(6,9).

paniq

% dominator analysis

% example from sedgewick, algorithms in C++, part 5, figure 19.21, §19.6, p. 191
% edge(from, to)
e(0,1). e(0,2). e(0,3). e(0,5). e(0,6).
e(2,3).
e(3,4). e(3,5).
e(4,9).
e(6,4). e(6,9).
e(7,6).

paniq

symbol(1,"the").
symbol(2,"quick").
symbol(3,"brown").
symbol(4,"fox").
symbol(5,"jumped").
symbol(6,"over").
symbol(7,"the").
symbol(8,"lazy").

paniq

L(23,1).
L(2,75).
L(5,75).
L(60,90).
L(5,101).
L(60,3).
L(707,66).
L(42,77).
L(5,15).

paniq

L(23).
L(60).
L(5).
L(707).
L(42).

adj(?a,#min(?b)) :- L(?a), L(?b), ?a < ?b.

paniq

Encoding polymorphic values (sum types) in the heap can be trivially done by a type code/index (or simply tag) in the value's header.

For large per-tag pools of monotypal objects, the pool range itself can serve as identifying the type. A pointer into the pool can be checked against all known pool extents to extract the tag. Unfortunately this makes memory relocation difficult, and prohibits the use of multiple pools for the same tag.

A better approach when the heap supports baseable pointers (such as arcmem), is to store the tag of a pool at its beginning; a pointer into the pool can then be based to the pool header, amortizing the cost of a type tag.

All three mentioned approaches suffer from the issue however that casts are expensive as we need to copy values just to change their type, even though the actual attributes of the value did not change.

For the case where the number of types for a sum type S is smaller than the alignment of S, which is invariant, the type index (or tag) can instead be stored