[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

5623–5624

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

5624–5627

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

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

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!

clang/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(); }
 
-  Stmt *getTerminatorCondition(bool StripParens = true);
+  /// \returns the condition of the terminator (condition of an if statement,
+  /// for loop, etc).
+  const Stmt *getTerminatorCondition(bool StripParens = true) const;
 
-  const Stmt *getTerminatorCondition(bool StripParens = true) const {
-    return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens);
+  const Expr *getTerminatorConditionExpr(bool StripParens = true) const {
+    return dyn_cast_or_null<Expr>(getTerminatorCondition(StripParens));
   }
 
   const Stmt *getLoopTarget() const { return LoopTarget; }
 
   Stmt *getLabel() { return Label; }
   const Stmt *getLabel() const { return Label; }
 
   bool hasNoReturnElement() const { return HasNoReturnElement; }

clang/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);
 }
 
-Stmt *CFGBlock::getTerminatorCondition(bool StripParens) {
-  Stmt *Terminator = getTerminatorStmt();
-  if (!Terminator)
+const Stmt *CFGBlock::getTerminatorCondition(bool StripParens) const {
+  // If the terminator is a temporary dtor or a virtual base, etc, we can't
+  // retrieve a meaningful condition, bail out.
+  if (rbegin()->getKind() != CFGElement::Kind::Statement)
     return nullptr;
 
-  Expr *E = nullptr;
-
-  switch (Terminator->getStmtClass()) {
-    default:
-      break;
-
-    case Stmt::CXXForRangeStmtClass:
-      E = cast<CXXForRangeStmt>(Terminator)->getCond();
-      break;
-
-    case Stmt::ForStmtClass:
-      E = cast<ForStmt>(Terminator)->getCond();
-      break;
-
-    case Stmt::WhileStmtClass:
-      E = cast<WhileStmt>(Terminator)->getCond();
-      break;
-
-    case Stmt::DoStmtClass:
-      E = cast<DoStmt>(Terminator)->getCond();
-      break;
-
-    case Stmt::IfStmtClass:
-      E = cast<IfStmt>(Terminator)->getCond();
-      break;
-
-    case Stmt::ChooseExprClass:
-      E = cast<ChooseExpr>(Terminator)->getCond();
-      break;
-
-    case Stmt::IndirectGotoStmtClass:
-      E = cast<IndirectGotoStmt>(Terminator)->getTarget();
-      break;
-
-    case Stmt::SwitchStmtClass:
-      E = cast<SwitchStmt>(Terminator)->getCond();
-      break;
-
-    case Stmt::BinaryConditionalOperatorClass:
-      E = cast<BinaryConditionalOperator>(Terminator)->getCond();
-      break;
-
-    case Stmt::ConditionalOperatorClass:
-      E = cast<ConditionalOperator>(Terminator)->getCond();
-      break;
-
-    case Stmt::BinaryOperatorClass: // '&&' and '||'
-      E = cast<BinaryOperator>(Terminator)->getLHS();
-      break;
-
-    case Stmt::ObjCForCollectionStmtClass:
-      return Terminator;
+  // This should be the condition of the terminator block.
+  const Stmt *S = rbegin()->castAs<CFGStmt>().getStmt();
+  if (isa<ObjCForCollectionStmt>(S)) {
+    return getTerminatorStmt();
   }
 
-  if (!StripParens)
-    return E;
-
-  return E ? E->IgnoreParens() : nullptr;
+  // Only ObjCForCollectionStmt is known not to be a non-Expr terminator.
+  const Expr *Cond = cast<Expr>(S);
+  return StripParens ? Cond->IgnoreParens() : Cond;
 }
 
 //===----------------------------------------------------------------------===//
 // CFG Graphviz Visualization
 //===----------------------------------------------------------------------===//
 
 #ifndef NDEBUG
 static StmtPrinterHelper* GraphHelper;