[RFC] Control-Depent Function Returns and Redefining Control Dependencies

[PBHDK]

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

[nlopes]

Can you explain a bit more of what you’re trying to do? Maybe it’s easier to start there than attempting to define dominators.
If you are looking to track which reads may depend on which writes we have MemorySSA.

[bmahjour]

@PBHDK

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.

The basic block containing WRITE_ONCE() (‘y’ in the textbook definition) is control dependent on the basic block that terminates with if(READ_ONCE(x)) ( ‘x’ in the textbook definition).

Assuming you structure/simplify your CFG so that all functions have a single exit block, there would be an edge from the basic block containing WRITE_ONCE() (‘y’) to that exit block. The exit block post-dominates every other basic block in the function including the basic block containing if(READ_ONCE(x)) (‘x’), but the basic block containing WRITE_ONCE() itself does not, so the “x is not post-dominated by y” is true here.

As for condition (1) in the text book definition, I believe “nontrivial path” means “x” is not the same basic block as “y”, and since there is just one edge going from x to y, there are no other (‘z’) basic blocks in this path to check to see if they are post-dominated by ‘y’, so this condition is true as well.

[jcranmer]

Redefining a term to mean something subtly but importantly different from the standard definition is a recipe for disaster.

Control-dependence is defined in terms of the postdominator tree. If you look at algorithms that rely on control-dependence, then this strict reliance on the postdominator tree is actually necessary. Note that where control-dependence is discussed, it’s actually necessary to consider that there is a pseudo-entry block which dominates the entry block, a pseudo-exit block which post dominates every return statement in the function and every loop with no exit blocks, and an additional pseudo-edge between the pseudo-entry and pseudo-exit block that bypasses the entire function. (I don’t have examples to hand of where this matters, but I know from experience that if you neglect this, your resulting control-dependence graph would lead you to erroneously conclude that some basic blocks have the same control dependencies in a few cases).

This definition does sometimes produce counterintuitive results in loops. But it’s important to remember that the standard control-flow-based definitions already produce counterintuitive results. Consider the following code:

while (1) {
  // ....
  if (test) {
    // Syntactically, this block is in the loop.
    // Query LoopInfo, and you'll find that this is *not* part of the loop, however.
    break;
  }
}

When a loop has a single exiting block, then that means that said block postdominates every basic block inside of a natural loop. This does cause the resulting control-dependence graph to be somewhat inverted compared to what you would naively expect from the corresponding if statements–everything in the loop is control-dependent on the loop exiting block, and things get extra spicy when the loop exiting block is not always executed every loop iteration. (I’d include diagrams here, but to my knowledge, Discourse still chokes on HTML emails, so there’s no way for me to do so). While this does look weird, when it comes time to relying on the resulting graph to make assertions about blocks–for example, basic blocks that share the same control-dependencies being such that if any one block is executed N times, all are executed exactly N times–the definition you get is correct, and trying to tweak it to make it look more “normal” leads to incorrect results.

In short, then, control-dependencies end up being counterintuitive when the condition you’re inquiring about is a condition that controls whether or not the loop will finish executing.

[PBHDK]

Thanks for all the replies, it really helps! (and sorry for getting back to you so late … )

@nlopes

Can you explain a bit more of what you’re trying to do?

In short, the Linux kernel defines its own notion of data, addr and ctrl dependencies [1]. I’m building / have built a mechanism for identifying them in IR.

@bmahjour

Assuming you structure/simplify your CFG so that all functions have a single exit block, there would be an edge from the basic block containing WRITE_ONCE() (‘y’) to that exit block.

Ah, in this case, the example was derived from optimised IR, and the BB containing the function return in the loop was the function’s single exit block. Single function return and WRITE_ONCE were located in the same BB.

@jcranmer

Redefining a term to mean something subtly but importantly different from the standard definition is a recipe for disaster.

Fair

@bmahjour

The basic block containing WRITE_ONCE() (‘y’ in the textbook definition) is control dependent on the basic block that terminates with if(READ_ONCE(x)) ( ‘x’ in the textbook definition).

@jcranmer

When a loop has a single exiting block, then that means that said block postdominates every basic block inside of a natural loop.

Sorry, I’m confused. You would agree that there is a control dependency here, but for LLVM’s purposes it is desirable (or at least not problematic) for the final BB in the loop to post-dominate all others, implying that there isn’t a control dependency?

Many thanks,
Paul

–
[1]: Documentation « memory-model « tools - kernel/git/stable/linux.git - Linux kernel stable tree

[bmahjour]

Single function return and WRITE_ONCE were located in the same BB.

Sorry I misunderstood the problem then. Since the only exit block is the one containing WRITE_ONCE(), it post-dominates if(READ_ONCE(x)), so the control-dependence does not hold.

It may seem less unintuitive if you consider that this CFG…

is semantically equivalent to this one:

[jcranmer]

Sorry, I’m confused. You would agree that there is a control dependency here, but for LLVM’s purposes it is desirable (or at least not problematic) for the final BB in the loop to post-dominate all others, implying that there isn’t a control dependency?

This is a bit hard to explain without diagrams that I can’t include (due to technological limitations), but let me have a go.

Consider a basic top-tested loop:

while (cond) {
  // Code
}

If you draw out the basic blocks of such a program and work out dominators, postdominators, and control-dependencies, it’s clear that every basic block within the loop is control-dependent on the condition of the loop. And this shouldn’t be surprising.

Move it to a bottom-tested loop:

do {
  // Code
} while(cond);

And it is still the case that everything in the loop is control-dependent on cond here.

Make it a middle-tested loop (note that C has no natural syntax for such a loop):

while (true) {
  // Code part 1
  If (!cond) break;
  // Code part 2
}

… and still everything in the loop is control-dependent on cond. We find that, no matter the form of the loop, with a single way to exit the loop, that exit condition naturally is a control-dependence for the entire loop body.

The confusion I think arises that if you change the last variant slightly so that your code looks like this:

while (true)  {
  a();
  if (cond) {
    b();
    break;
  }
  c();
}

It syntactically looks like b() ought to be control-dependent on cond. However, notice that this example is structurally equivalent to this form:

while (true)  {
  a();
  if (cond) {
    break;
  }
  c();
}
b();

It should be clear then that b() should not be control-dependent on anything in the loop.

[PBHDK]

Thank you both for clarifying!

This appears to be a prime example for showing that the Linux kernel and LLVM simply have different objectives for their respective definitions of control dependencies. (If I’m not mistaken ;-))

LLVM is concerned with control-flow dependence in the control flow graph, i.e. is there theoretically a way for control flow to avoid execution of a given BB / instruction on the way to a / the function return based on a conditional branch? If yes, there is a control dependency. This is a static definition, and we can always give a definite yes / no answer at compile-time.

The Linux kernel’s definition of a control dependency on the other hand is meant, to the best of my understanding, as a means for making predictions about ordering of certain instructions (READ_ONCE / WRITE_ONCE() in my first post) at runtime.

This will often amount to the same results, with one exception being the loop we discussed above. The Linux kernel sees a control dependency here. LLVM, with its static definition serving a different purpose, doesn’t.

Thank you all for the detailed responses - they helped and are much appreciated!

Paul