Proposal for building CFG that includes representation for parallel threads and synchronized barriers

[paili0628]

In order to do DRF(data-race-free) analysis for calyx program, we need a flattened graph representation for our control program, for which individual groups and component invokes, which are considered atomic when executing the program, are represented by nodes, and control flow(in this case, seq, par, while, and if) are represented by a combination of nodes and edges. Listed below are representations for enable,seq, par, while, if, invoke, and the @sync annotation.

enable
enable is just represented as a single node of the group that's enabled.

invoke
invoke is just represented as a single node containing the cell being invoked.

seq
We represent seq as a seq header node followed by the sequence of subgraphs generated for control statements wrapped inside the seq block, connected by 1 edge in between the subgraph of each two consecutive control statements, and followed by a seq_end node. For instance, for the control program below,

seq {
--control_1--;
--control_2--;
}

the CFG will look like graph (1).

par
We represent par as a par header node, which has an edge that goes to all subgraphs of statements wrapped inside the par block, respectively. The end of subgraphs of the statements then all have an outgoing edge connected to the par_end node. For the control program below,

par {
--control_1--;
--control_2--;
}

the CFG will look like graph (2).

if
if branches are represented as an if header node, which in itself includes the group and port for the condition. It also has two conditional outgoing edges, which point to the subgraphs for the true and false branches, respectively. The end of the two subgraphs point to the if_end node. For the control program below,

if cond.out with comp {
--control_1--;
}
else {
--control_2--;
}

the CFG will look like graph (3).

while
while loops have a similar representation as the if statement. It also has a while header node, which also knows about the group and port for the condition evaluation. It also has two conditional outgoing edges. However, only the true edge points to the subgraph of the while body; the false path points directly to the while_end node. Also, the end of the while body does not point to the while_end node. Instead, it again points to the while header node, resulting a representation for loop that we want.
For the control program below,

while cond.out with comp {
--control_1--;
}

graph (4) is the corresponding CFG representation.

@sync
@syncis represented as a sync node that has an incoming edge from the end of the subgraph of each control marked with @sync. All control statements marked with @sync, then has an outgoing edge not only to its subsequent control subgraph but also to the sync node.
For the control program below,

par {
while cond.out with comp {
seq {
@sync(1) --control_1--;
--control_2--;
}
}
while cond.out with comp {
seq {
--control_3--;
@sync(1) --control_4--;
}
}
}

graph (5) is the corresponding CFG representation.

*Notice that while the circles in the above graph represent individual nodes, the squares in fact represent subgraphs for control statements, which may not consist of only one node.

[rachitnigam]

Cool proposal! One thing we should consider is unifying the notion of "control edges" and "seq edges" and just say that edges between two seq children have the condition "true" which means that edge is always taken. The kind of graph that you're proposing is very close to control-dataflow graph (CDFG) such as the one used in LLVM which uses single static assignment (SSA). We should take a lot of inspiration from it and try to mirror ideas from it as much as possible.

SSA generally doesn't handle parallel edges or sync edges so we need special handling for them. As we discussed, par blocks are just a special case of @sync annotations so again, we should unify those two ideas. I like the idea of a sync node explicitly represented in the graph because it represents the transition of control flow explicitly. It should also be able to encode a par block as a sync node at the start and the end of the threads.