This is an archive of the discontinued LLVM Phabricator instance.

[CFG] Add a new function to get the proper condition of a CFGBlock
ClosedPublic

Authored by Szelethus on Jun 19 2019, 2:46 AM.

Details

Summary

For the following terminator statement:

if (A && B && C && D)

The built CFG is the following:

[B5 (ENTRY)]
  Succs (1): B4

[B1]
  1: 10
  2: j
  3: [B1.2] (ImplicitCastExpr, LValueToRValue, int)
  4: [B1.1] / [B1.3]
  5: int x = 10 / j;
  Preds (1): B2
  Succs (1): B0

[B2]
  1: C
  2: [B2.1] (ImplicitCastExpr, LValueToRValue, _Bool)
  T: if [B4.4] && [B3.2] && [B2.2]
  Preds (1): B3
  Succs (2): B1 B0

[B3]
  1: B
  2: [B3.1] (ImplicitCastExpr, LValueToRValue, _Bool)
  T: [B4.4] && [B3.2] && ...
  Preds (1): B4
  Succs (2): B2 B0

[B4]
  1: 0
  2: int j = 0;
  3: A
  4: [B4.3] (ImplicitCastExpr, LValueToRValue, _Bool)
  T: [B4.4] && ...
  Preds (1): B5
  Succs (2): B3 B0

[B0 (EXIT)]
  Preds (4): B1 B2 B3 B4

However, even though the path of execution in B2 only depends on C's value, CFGBlock::getCondition() would return the entire condition (A && B && C). For B3, it would return A && B. The new function only returns C.

Diff Detail

Event Timeline

Szelethus created this revision.Jun 19 2019, 2:46 AM
NoQ added a comment.Jun 19 2019, 5:34 PM

I think this kinda makes sense, but also it looks like a risky change, because who knows how many times we have took the old behavior for granted. In particular, i'm slightly worried about this breaking the wonky logic of ExprEngine::VisitLogicalExpr (cf. D59857). But i've no specific concerns, so i think it's worth a try, given that it's a massive simplification.

clang/lib/Analysis/CFG.cpp
5687–5691

Can we do the assignment to the previous line pls? ^.^

5692–5695

The new arrow doesn't really make much sense. Like, there's nothing interesting going on specifically with the collection, so there's no reason to highlight it separately from, say, the element we're extracting from it. Let's just keep the old behavior.

Szelethus updated this revision to Diff 205909.Jun 20 2019, 3:00 PM

Addressing reviewer feedback!

Szelethus marked 2 inline comments as done.Jun 20 2019, 3:00 PM
NoQ accepted this revision.Jun 20 2019, 3:03 PM

Ok, thanks!

This revision is now accepted and ready to land.Jun 20 2019, 3:03 PM

This change will be really useful for the lifetime analysis as well! Thanks!

I have one concern though. The analyzer is using linerarized (or threaded) CFGs with every subexpression being a separate entry in the basic blocks. Will your change give sensible answers for non-linearized CFGs? If not, this should be documented. Do we have users of this API with non-linearized CFGs?

Szelethus planned changes to this revision.Jul 2 2019, 8:54 AM

Something's off. test/Analysis/edges-new.mm fails, but I don't remember any test failures at home -- I'll investigate.

Before this patch:


After this patch:

Szelethus requested review of this revision.Jul 3 2019, 5:49 AM

Seems fine over here.... let's see what happens if I try to land it?

This revision is now accepted and ready to land.Jul 3 2019, 5:49 AM
This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptJul 3 2019, 5:54 AM
Szelethus reopened this revision.Jul 3 2019, 6:30 AM

Causes crashes on Sema.

This revision is now accepted and ready to land.Jul 3 2019, 6:30 AM
Szelethus updated this revision to Diff 207833.Jul 3 2019, 10:28 AM
Szelethus retitled this revision from [analyzer][CFG] Return the correct terminator condition to [CFG] Add a new function to get the proper condition of a CFGBlock.
Szelethus edited the summary of this revision. (Show Details)

Let's not try to tinker with something in a way that could have unforeseen consequences. I added a new method to simply get the condition the way I (and probably @xazax.hun) will need it.

Szelethus requested review of this revision.Jul 3 2019, 10:29 AM
NoQ added inline comments.Jul 3 2019, 11:18 AM
clang/lib/Analysis/CFG.cpp
5619–5625

I don't think you're looking at the terminator here, as CFGTerminator isn't a sub-class of CFGElement. So this if doesn't avoid temporary dtor branches or virtual base branches; instead, it avoids various other CFGElement sub-classes such as CFGInitializer or CFGImplicitDtor (not sure how many of those may appear last in a block).

Therefore the following code would be a bit more LLVM-y:

auto StmtElem = rbegin()->getAs<CFGStmt>();
if (!StmtElem)
  return nullptr;

const Stmt *S = StmtElem->getStmt();

Also, are you sure that the last expression is always a condition? Like, what about

void foo(int x, int y) {
  (void)(x + y);
}

?

xazax.hun added inline comments.Jul 3 2019, 11:26 AM
clang/lib/Analysis/CFG.cpp
5619–5625

The question is, is CFGTerminator is what we are looking for? I think the point of the method is to get the last subexpression that was evaluated before taking a branch.

For the condition, would it make sense to check the number of successors (before pruning the trivially false branches)? If less than or equal to 1 it is probably not a condition. Otherwise maybe we could just rename it to last evaluated (sub)expression. The sub-part might depend on whether we use a linearized CFG.

Szelethus updated this revision to Diff 207902.Jul 3 2019, 3:34 PM
  • Bail out if the actual terminator isn't a branch
  • Bail out if the number of successors is less than 2
  • LLVM-ify the code as suggested!
  • Add some unit tests (I mean, you can kinda see how it was duct taped together, but it's maybe a hair better than nothing?)
Szelethus updated this revision to Diff 207904.Jul 3 2019, 3:39 PM

Add one more assert to GetExprText.

Szelethus marked 3 inline comments as done.Jul 4 2019, 11:30 AM
NoQ accepted this revision.Jul 4 2019, 7:48 PM

Looks great, thanks!

This revision is now accepted and ready to land.Jul 4 2019, 7:48 PM
This revision was automatically updated to reflect the committed changes.

Apologies, I thought my followup commit fixed the issue -- No other other platforms seem to suffer (not even sanitizer builds) -- what does SEH exception mean in this case? I did look up on it but found nothing concrete.

Since the followup patches test this roughly anyways, and the fact that the AST's lifetime ends right after the CFG's construction makes the remaining tests pretty much pointless, if I can't resolve this, I'll just remove the testfile. Would you like me to go ahead with that right away?

Since the followup patches test this roughly anyways, and the fact that the AST's lifetime ends right after the CFG's construction makes the remaining tests pretty much pointless, if I can't resolve this, I'll just remove the testfile.

I mean, this is a good enough reason to just go through with it. Removed in rL365209. Sorry for the inconvenience!

Since the followup patches test this roughly anyways, and the fact that the AST's lifetime ends right after the CFG's construction makes the remaining tests pretty much pointless, if I can't resolve this, I'll just remove the testfile.

I mean, this is a good enough reason to just go through with it. Removed in rL365209. Sorry for the inconvenience!

Thanks!