Hi all,
For a project in the context of the Linux kernel, I have been working on tracking address, control and data dependencies on IR-level, using two module passes.
To cut a long story short, I came across the following example of a control dependency. The pseudo code is based on some optimised IR. Think of READ_ONCE() and WRITE_ONCE() as atomic reads / writes:
int *x, *y;
int foo()
{
/* More code */loop:
/* More code */if(READ_ONCE(x)) {
WRITE_ONCE(y, 42);
return 0;
}/* More code */
goto loop;
/* More code */
}
I have seen control dependencies being defined in terms of the first
basic block that post-dominates the basic block of the if-condition,
that is the first basic block control flow must take to reach the
function return regardless of what the if condition returned.
E.g. [1] defines control dependencies as follows:
A statement y is said to be control dependent on another statement x
if (1) there exists a nontrivial path from x to y such that every
statement z != x in the path is post-dominated by y, and (2) x is not
post-dominated by y.
However, assuming that foo() will return, the above definition of control dependencies cannot be applied here as the WRITE_ONCE() is in the same basic block as the return statement. It therefore trivially post-dominates all other BB’s => no control dependency.
Here is an alternative definition I came up with:
A basic block B is control-dependent on a basic block A if
B is reachable from A, but control flow can take a path through A
which avoids B. The scope of a control dependency ends at the first
basic block where all control flow paths running through A meet.
I had tried using LLVM’s PostDominatorTrees for the above case, but without luck, which is why I adapted my definition.
What do you think? I might be missing something here. Comments and pointers very welcome
I have also shared the above on the Linux kernel mailing list in case anyone is interested [2].
Many thanks,
Paul
–
[1]: Optimizing Compilers for Modern Architectures: A Dependence-Based
Approach, Randy Allen, Ken Kennedy, 2002, p. 350
[2]: [PATCH RFC] tools/memory-model: Adjust ctrl dependency definition - Paul Heidekrüger