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.
fn fib (n : i64) -> i64 {
x0, x1 : i64;
repeat : ();
__entry -> n;
n -> {
1:i64 -> x1;
}
n -> {
0:i64 -> x0;
}
x0, x1, n -> {
%1 = n > 0:i64;
case %1 == true;
() -> repeat;
}
repeat, x1 -> {
x1 -> x0;
}
repeat, x0, x1 -> {
%1 = x0 + x1;
%1 -> x1;
}
repeat, n -> {
%1 = n - 1:i64;
%1 -> n;
}
!repeat, x0 -> {
x0 -> __return;
}
}
The BBB flow graph is a digraph G : (Ve : {event, ...}, Vb : {block, ...}, Eeb : {event->block, ...}, Erd : {block->event, ...}) that connects vertices V (from here on called "nodes") of type event | block with unlabeled edges E of type event->block | block->event. A block node depends on all of one or more event nodes but must merge to exactly one event node. An event node therefore depends on, and is a dependant of, any of one or more block nodes.
An event node, or simply "event" [merge(F)] X : T, labels a static runtime value X of arbitrary option type T. During execution, X is conceptually mapped to values of the sum type defined(ET) | undefined, where ET is the element type of the option. An event node E is only updated if a block that targets E has been updated.
Where X is concurrently merged to by two or more block nodes, an aggregate function F(&T, T) -> () must be specified by the merge() qualifier that implements a conflict resolution strategy. In the simplest case where T is of platform integer type, F can simply be one of the atomic arithmetic operators.
By convention, each program or function execution begins with an implicitly defined entry point event __entry : () of empty tuple element type, upon which all blocks to be executed first depend. Within function envelopes, an implicit return event __return : T selects the value to be returned by the function.
A block node, or simply "block" <event-list> -> { [<assignment-list>] [<case-list>] <terminator> } declares the edges of the graph and describes a time-linear update rule which translates availability of events to side effects and conditional update of one successive event.
<event-list> specifies a list of events that need to be defined to meet the block's conditions for execution. In addition, a block is only updated if at least one of the events in <event-list> has been updated. <assignment-list> is a list of classical SSA instructions to be executed in order of declaration. Unlike with CFG, instructions are block-private and may not be referenced by instructions in other blocks. In addition to constants, globals and previously assigned values in the same block, instructions may reference events listed in <event-list>, which at the time of execution are guaranteed to be defined().
<terminator> is a single instruction <value> -> <event> which binds the block to defined(<value>), to be merged by the successor <event>. <case-list> is a list of switch-style case <condition> == <constant> predicates. If any predicate evaluates to false, or any event in <event-list> is undefined, the block is bound to undefined.
In a pure acyclic BBB, events stratify, which means an event delays aggregating its values to a point where all source block values have been determined either way. However, once blocks have been declared which (implicitly) depend on their successor, complete aggregation is no longer possible since an event now depends on block values that are yet to be computed. The graph is no longer acyclic. To solve this problem, we heuristically tag such blocks as upstream during update execution planning.
When an event E is updated from a block P whose maximum distance to __entry is smaller than E, E will only aggregate its downstream block values. When updated from a upstream block, events then only aggregate upstream block values. These two update paths are applied in conjunction, but with upstream taking precedence over downstream, which matters for merge functions with "overwrite" behavior.