Leonard Ritter paniq

BBB: Broadcasting Basic Blocks

Leonard Ritter, Duangle GbR

Last change 2024/08/17, first version 2024/07/23

With the Broadcasting Basic Blocks form, we extend Static single-assignment form with pure functional concurrent semantics that replace and generalize the traditional Control Flow Graph. In BBB, Φ functions and values shared between basic blocks are replaced with events of arbitrary option type, on which basic blocks specify dependencies. Basic block terminators simplify to a single conditional merge. Based on event dependency constraints, a topologically ordered and partially stratified update execution plan then lowers BBB to a control flow graph.

Listing 1: BBB representation of a function fib computing values from the Fibonacci series.

Relation-Rule Based Callgraph Inference

2024/07/23 Leonard Ritter, Duangle GbR

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.

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)

	// top level is a throwaway heap object
	// first heap object to be declared at the top level is the root object

	// aligned concat (using alignment of token2)
	<token1> , <token2>

	// 1-byte packed concat (token2 alignment is treated as if 1)
	<token1> <token2>

	// zero-pad stream to largest aligned member since last statement or beginning of scope (struct alignment)

	pg := DRIL:
	enum Place : i64
	Foyer
	LivingRoom
	Office
	Kitchen
	Bedroom
	Bathroom
	Cellar

	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)

	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

	% 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).

	% 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).



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