CFG structure for short-circuiting logical operators

Clang Frontend Static Analyzer
1

I’m working on fixing a crash in the dataflow framework that occurs while analyzing a condition containing multiple short-circuiting logical operators, and I have a question on why the CFG for these has the specific structure that it does. I believe the crash happens because the dataflow framework makes assumptions about the structure of the CFG that aren’t actually guaranteed by the CFG code.

Here is a minimal repro for my problem:

(Yes, this is the minimal repro – the issue needs three || operators to reproduce and doesn’t occur with only two.)

Some notes on the structure of the CFG:

  • [B5], which evaluates the true literal, is reachable

  • [B2], [B3] and [B4], which evaluate the three false literals, are not reachable

  • The BinaryOperator expressions for the first two || operators are only contained in the CFG as terminators – they do not appear anywhere as a normal (non-terminator) expression. Only the third BinaryOperator expression (for the last || operator) appears as a non-terminator expression ([B1.1]). (The pretty-printed version of this expression reads [B5.1] || [B4.1] || [B3.1] || [B2.1], but the actual underlying Expr referred to by the CFGElement is merely the last || operator.)

This last fact is what causes the issue in the dataflow framework. The framework assumes that every reachable Expr will appear in some reachable CFG block, and the dataflow analysis processes those expressions that appear in reachable CFG blocks (either as a normal or terminator expression). The middle BinaryOperator does not, however, appear anywhere in a reachable CFG block, and this is what causes the issue.

Questions

Can someone confirm that I am correct about the following three points?

  • I believe the underlying assumption – that every reachable Expr will appear in some reachable CFG block – is not actually guaranteed by the CFG, at least when it comes to short-circuiting logical operators.

  • The intent behind marking [B3] and [B4] as unreachable is to indicate that the false literals in these blocks are unreachable (which is correct), but not to indicate that the terminators of these blocks (the || operators) are unreachable (which would not be correct, because these expressions as a whole still need to be evaluated, even if their right-hand sides don’t need to be). This makes sense because, as noted in the documentation for CFGBlock, the terminator is not considered to be part of the set of statements contained in the block.

  • I therefore believe the intent behind the CFG’s construction is that, when visiting [B1.1], the entire expression tree for [B5.1] || [B4.1] || [B3.1] || [B2.1] should be evaluated. A consumer of the CFG cannot, in other words, assume that sub-expressions of a reachable expression tree have appeared elsewhere as a reachable expression, either earlier in the same CFG block or in a preceding reachable CFG block.

An additional note: If we rewrite the example above using ternary operators (where x || y is rewritten into the functionally equivalent x ? true : y), then it is in fact true that every reachable expression appears in some reachable CFG block:

One might therefore expect the short-circuiting logical operators to result in an equivalent CFG structure, but this is not the case, and it appears that this inconsistency is intentional – correct?

2

@sgatev I’m told you may have some context on this?

3

I think the assumption we want to make is stronger. We want reachable Exprs not just to appear somewhere in any reachable basic block, we want them to appear in the correct spot of each relevant execution path. Said differently, we want that every Expr that is formally evaluated by the C++ abstract machine on a given execution path to be also visited when we perform abstract interpretation of the same path using the CFG.

So, if we speak of this example:

bool f() { return true || false || false || false; }

Let’s fully parenthesize it to remove any possible ambiguity, and label the expressions:

//                   E1  Op1  E2   Op2  E3   Op3  E4
bool f() { return ((true || false) || false) || false; }

There is only one execution path that the C++ abstract machine can take before returning from the function:

E1 -> Op1 -> Op2 -> Op3

Thus, we want all of these expressions to appear in the CFG when we traverse this execution path. But right now Op2 does not appear in the CFG on this path.

CC @Xazax-hun @NoQ

4

I fully agree with Dmitri about the desired behavior, but I have a couple of additional questions.

This is only a problem when PruneTriviallyFalseEdges option is used, right? Are we willing to generate Cfgs with a different shape based on this option or are you proposing changing the shape of the Cfg regardless of this option? Do we need this option at all? What are the use cases for not pruning trivially false edges? Do we want to emit flow-sensitive warnings for dead code?

5

This problem only actively hurts the dataflow framework when this option is used, which is why we have newly discovered it when we turned this option on recently.

The exact reasons why it only blew up after we turned on this option are complicated and not worth discussing. There is even a special case hack in Transfer.cpp specifically which covers up this problem when PruneTriviallyFalseEdges=false. It is a hack because there should never be a reason to recursively look at the children, we should only ever look at the immediate children.

6

Agreed. This is would also be consistent with the CFG that we get if we rewrite || into the equivalent ternary operator – see the godbolt I referenced in the OP:

7

The consequences are particularly bad with PruneTriviallyFalseEdges, but as Dmitri has pointed out, even without that option set, we require a special-case hack to visit children of the current Expr recursively.

Assuming it’s realistic to change the shape of the CFG (i.e. there isn’t too much existing client code that depends on the current shape of the CFG), I would propose changing the shape of the CFG regardless of this option.

I’m not sure what the use cases are here. My assumption is that PruneTriviallyFalseEdges can be turned off simply for efficiency. Setting PruneTriviallyFalseEdges doesn’t lose any information – it merely marks unreachable edges as such, so if the consumer of the CFG wants to visit dead code, it can just treat unreachable edges the same as reachable edges.

That said, PruneTriviallyFalseEdges isn’t really even a big consideration here: As stated above, if the shape of the CFG changes, I think it should change regardless of this option.

8

Thanks for the clarifications, I strongly support changing the shape of the CFG to make it easier to use (regardless of the configuration options used). I hope that most users do not rely on the shape too much and the fallout would not be too bad.