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

[Szelethus]

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.

[NoQ]

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

5628–5630 ↗

(On Diff #205517)

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

5631–5634 ↗

(On Diff #205517)

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]

Addressing reviewer feedback!

[NoQ]

Ok, thanks!

[xazax.hun]

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]

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]

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

[Szelethus]

Causes crashes on Sema.

[Szelethus]

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.

[NoQ]

clang/lib/Analysis/CFG.cpp

5619–5625 ↗

(On Diff #207833)

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]

clang/lib/Analysis/CFG.cpp

5619–5625 ↗

(On Diff #207833)

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]

• 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]

Add one more assert to GetExprText.

[NoQ]

Looks great, thanks!

[RKSimon]

@Szelethus This is causing problems on windows buildbots http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast - revert?

[Szelethus]

In D63538#1571418, @RKSimon wrote:

@Szelethus This is causing problems on windows buildbots http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast - revert?

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?

[Szelethus]

In D63538#1571451, @Szelethus wrote:

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!

[RKSimon]

In D63538#1571454, @Szelethus wrote:

In D63538#1571451, @Szelethus wrote:

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!

cfe/trunk/include/clang/Analysis/CFG.h

public:
   void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
   void setHasNoReturnElement() { HasNoReturnElement = true; }
 
   CFGTerminator getTerminator() const { return Terminator; }
 
   Stmt *getTerminatorStmt() { return Terminator.getStmt(); }
   const Stmt *getTerminatorStmt() const { return Terminator.getStmt(); }
 
+  /// \returns the last (\c rbegin()) condition, e.g. observe the following code
+  /// snippet:
+  ///   if (A && B && C)
+  /// A block would be created for \c A, \c B, and \c C. For the latter,
+  /// \c getTerminatorStmt() would retrieve the entire condition, rather than
+  /// C itself, while this method would only return C.
+  const Expr *getLastCondition() const;
+
   Stmt *getTerminatorCondition(bool StripParens = true);
 
   const Stmt *getTerminatorCondition(bool StripParens = true) const {
     return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens);
   }
 
   const Stmt *getLoopTarget() const { return LoopTarget; }
 

cfe/trunk/lib/Analysis/CFG.cpp

void CFGBlock::printTerminatorJson(raw_ostream &Out, const LangOptions &LO,
   std::string Buf;
   llvm::raw_string_ostream TempOut(Buf);
 
   printTerminator(TempOut, LO);
 
   Out << JsonFormat(TempOut.str(), AddQuotes);
 }
 
+const Expr *CFGBlock::getLastCondition() const {
+  // If the terminator is a temporary dtor or a virtual base, etc, we can't
+  // retrieve a meaningful condition, bail out.
+  if (Terminator.getKind() != CFGTerminator::StmtBranch)
+    return nullptr;
+
+  // Also, if this method was called on a block that doesn't have 2 successors,
+  // this block doesn't have retrievable condition.
+  if (succ_size() < 2)
+    return nullptr;
+
+  auto StmtElem = rbegin()->getAs<CFGStmt>();
+  if (!StmtElem)
+    return nullptr;
+
+  const Stmt *Cond = StmtElem->getStmt();
+  if (isa<ObjCForCollectionStmt>(Cond))
+    return nullptr;
+
+  // Only ObjCForCollectionStmt is known not to be a non-Expr terminator, hence
+  // the cast<>.
+  return cast<Expr>(Cond)->IgnoreParens();
+}
+
 Stmt *CFGBlock::getTerminatorCondition(bool StripParens) {
   Stmt *Terminator = getTerminatorStmt();
   if (!Terminator)
     return nullptr;
 
   Expr *E = nullptr;
 
   switch (Terminator->getStmtClass()) {

cfe/trunk/unittests/Analysis/CFGTest.cpp

TEST(CFG, IsLinear) {
   expectLinear(true,  "void foo() { if constexpr (false); }");
   expectLinear(false, "void foo(bool coin) { if (coin) return; }");
   expectLinear(false, "void foo() { for(;;); }");
   expectLinear(false, "void foo() { do {} while (true); }");
   expectLinear(true,  "void foo() { do {} while (false); }");
   expectLinear(true,  "void foo() { foo(); }"); // Recursion is not our problem.
 }
 
+TEST(CFG, ConditionExpr) {
+  const char *Code = R"(void f(bool A, bool B, bool C) {
+                          if (A && B && C)
+                            int x;
+                        })";
+  BuildResult Result = BuildCFG(Code);
+  EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+
+  // [B5 (ENTRY)] -> [B4] -> [B3] -> [B2] -> [B1] -> [B0 (EXIT)]
+  //                   \      \       \                 /
+  //                    ------------------------------->
+
+  CFG *cfg = Result.getCFG();
+
+  auto GetBlock = [cfg] (unsigned Index) -> CFGBlock * {
+    assert(Index < cfg->size());
+    return *(cfg->begin() + Index);
+  };
+
+  auto GetExprText = [] (const Expr *E) -> std::string {
+    // It's very awkward trying to recover the actual expression text without
+    // a real source file, so use this as a workaround. We know that the
+    // condition expression looks like this:
+    //
+    // ImplicitCastExpr 0xd07bf8 '_Bool' <LValueToRValue>
+    //  `-DeclRefExpr 0xd07bd8 '_Bool' lvalue ParmVar 0xd07960 'C' '_Bool'
+
+    assert(isa<ImplicitCastExpr>(E));
+    assert(++E->child_begin() == E->child_end());
+    const auto *D = dyn_cast<DeclRefExpr>(*E->child_begin());
+    return D->getFoundDecl()->getNameAsString();
+  };
+
+  EXPECT_EQ(GetBlock(1)->getLastCondition(), nullptr);
+  EXPECT_EQ(GetExprText(GetBlock(4)->getLastCondition()), "A");
+  EXPECT_EQ(GetExprText(GetBlock(3)->getLastCondition()), "B");
+  EXPECT_EQ(GetExprText(GetBlock(2)->getLastCondition()), "C");
+
+  //===--------------------------------------------------------------------===//
+
+  Code = R"(void foo(int x, int y) {
+              (void)(x + y);
+            })";
+  Result = BuildCFG(Code);
+  EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+
+  // [B2 (ENTRY)] -> [B1] -> [B0 (EXIT)]
+
+  cfg = Result.getCFG();
+  EXPECT_EQ(GetBlock(1)->getLastCondition(), nullptr);
+}
+
 } // namespace
 } // namespace analysis
 } // namespace clang