[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-17 Thread via cfe-commits 

https://github.com/martinboehme edited 
https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-17 Thread via cfe-commits 


@@ -53,19 +52,8 @@ static int blockIndexInPredecessor(const CFGBlock ,
   return BlockPos - Pred.succ_begin();
 }
 
-static bool isLoopHead(const CFGBlock ) {
-  if (const auto *T = B.getTerminatorStmt())
-switch (T->getStmtClass()) {
-  case Stmt::WhileStmtClass:
-  case Stmt::DoStmtClass:
-  case Stmt::ForStmtClass:
-  case Stmt::CXXForRangeStmtClass:
-return true;
-  default:
-return false;
-}
-
-  return false;
+static bool isBackedgeNode(const CFGBlock ) {

martinboehme wrote:

Yes, but

* It still requires work (not everyone has an IDE with great cross-linking, so 
this could be multiple clicks), and
* 
* We're introducing a new term here ("backedge node"), and it's not clear 
without an explanation whether a) we intend for this to be a synonym for "has 
loop target" (but then why aren't we reusing that term -- is it because we 
think "backedge node" is clearer?), or b) `getLoopTarget() != nullptr` happens 
to be the right implementation today, but we think it might change in the 
future, so we're wrapping this check in a function?

https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-16 Thread Yitzhak Mandelbaum via cfe-commits 

https://github.com/ymand closed https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-16 Thread Yitzhak Mandelbaum via cfe-commits 


@@ -53,19 +52,8 @@ static int blockIndexInPredecessor(const CFGBlock ,
   return BlockPos - Pred.succ_begin();
 }
 
-static bool isLoopHead(const CFGBlock ) {
-  if (const auto *T = B.getTerminatorStmt())
-switch (T->getStmtClass()) {
-  case Stmt::WhileStmtClass:
-  case Stmt::DoStmtClass:
-  case Stmt::ForStmtClass:
-  case Stmt::CXXForRangeStmtClass:
-return true;
-  default:
-return false;
-}
-
-  return false;
+static bool isBackedgeNode(const CFGBlock ) {

ymand wrote:

https://github.com/llvm/llvm-project/blob/eb14f47bf1ccfda500ba3c3092d70e269f6f0b56/clang/include/clang/Analysis/CFG.h#L805

Fwiw, I think this comment is better than the one in the CFG, so I don't know 
that linking is worth much, especially since it can be found pretty easily just 
by looking at `getLoopTarget`.

https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-16 Thread Yitzhak Mandelbaum via cfe-commits 

https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/68923

>From 83486a35e6d0e754dd99369fc546d04afedbe923 Mon Sep 17 00:00:00 2001
From: Yitzhak Mandelbaum 
Date: Thu, 12 Oct 2023 19:35:54 +
Subject: [PATCH 1/3] [clang][dataflow] Check for backedges directly (instead
 of loop statements).

Widen on backedge nodes, instead of nodes with a loop statement as terminator.
This fixes #67834 and a precision loss from assignment in a loop condition. The
commit contains tests for both of these issues.
---
 .../TypeErasedDataflowAnalysis.cpp| 29 ++-
 .../Analysis/FlowSensitive/TransferTest.cpp   | 14 +
 .../TypeErasedDataflowAnalysisTest.cpp| 28 ++
 3 files changed, 51 insertions(+), 20 deletions(-)

diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp 
b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
index 6b167891c1a3ac8..5da3a5b1ccf8a2c 100644
--- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -12,7 +12,6 @@
 
//===--===//
 
 #include 
-#include 
 #include 
 #include 
 #include 
@@ -33,8 +32,8 @@
 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallBitVector.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 
@@ -53,19 +52,8 @@ static int blockIndexInPredecessor(const CFGBlock ,
   return BlockPos - Pred.succ_begin();
 }
 
-static bool isLoopHead(const CFGBlock ) {
-  if (const auto *T = B.getTerminatorStmt())
-switch (T->getStmtClass()) {
-  case Stmt::WhileStmtClass:
-  case Stmt::DoStmtClass:
-  case Stmt::ForStmtClass:
-  case Stmt::CXXForRangeStmtClass:
-return true;
-  default:
-return false;
-}
-
-  return false;
+static bool isBackedgeNode(const CFGBlock ) {
+ return B.getLoopTarget() != nullptr;
 }
 
 namespace {
@@ -502,14 +490,15 @@ runTypeErasedDataflowAnalysis(
 PostVisitCFG) {
   PrettyStackTraceAnalysis CrashInfo(CFCtx, "runTypeErasedDataflowAnalysis");
 
-  PostOrderCFGView POV(());
-  ForwardDataflowWorklist Worklist(CFCtx.getCFG(), );
+  const clang::CFG  = CFCtx.getCFG();
+  PostOrderCFGView POV();
+  ForwardDataflowWorklist Worklist(CFG, );
 
   std::vector> BlockStates(
-  CFCtx.getCFG().size());
+  CFG.size());
 
   // The entry basic block doesn't contain statements so it can be skipped.
-  const CFGBlock  = CFCtx.getCFG().getEntry();
+  const CFGBlock  = CFG.getEntry();
   BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
  InitEnv.fork()};
   Worklist.enqueueSuccessors();
@@ -553,7 +542,7 @@ runTypeErasedDataflowAnalysis(
 llvm::errs() << "Old Env:\n";
 OldBlockState->Env.dump();
   });
-  if (isLoopHead(*Block)) {
+  if (isBackedgeNode(*Block)) {
 LatticeJoinEffect Effect1 = Analysis.widenTypeErased(
 NewBlockState.Lattice, OldBlockState->Lattice);
 LatticeJoinEffect Effect2 =
diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp 
b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
index 632632a1b30e78b..7c697fa5f87d941 100644
--- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
@@ -4099,6 +4099,20 @@ TEST(TransferTest, 
LoopDereferencingChangingRecordPointerConverges) {
   ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
 }
 
+TEST(TransferTest, LoopWithDisjunctiveConditionConverges) {
+  std::string Code = R"cc(
+bool foo();
+
+void target() {
+  bool c = false;
+  while (foo() || foo()) {
+c = true;
+  }
+}
+  )cc";
+  ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
+}
+
 TEST(TransferTest, DoesNotCrashOnUnionThisExpr) {
   std::string Code = R"(
 union Union {
diff --git 
a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp 
b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
index 2425bb8711bdbaf..6800d736afd9b08 100644
--- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
@@ -913,6 +913,34 @@ TEST_F(FlowConditionTest, WhileStmt) {
   });
 }
 
+TEST_F(FlowConditionTest, WhileStmtWithAssignmentInCondition) {
+  std::string Code = R"(
+void target(bool Foo) {
+  // This test checks whether the analysis preserves the connection between
+  // the value of `Foo` and the assignment expression, despite widening.
+  // The equality operator generates a fresh boolean variable on each
+

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-16 Thread Yitzhak Mandelbaum via cfe-commits 


@@ -502,14 +490,15 @@ runTypeErasedDataflowAnalysis(
 PostVisitCFG) {
   PrettyStackTraceAnalysis CrashInfo(CFCtx, "runTypeErasedDataflowAnalysis");
 
-  PostOrderCFGView POV(());
-  ForwardDataflowWorklist Worklist(CFCtx.getCFG(), );
+  const clang::CFG  = CFCtx.getCFG();
+  PostOrderCFGView POV();
+  ForwardDataflowWorklist Worklist(CFG, );
 
   std::vector> BlockStates(
-  CFCtx.getCFG().size());
+  CFG.size());
 
   // The entry basic block doesn't contain statements so it can be skipped.
-  const CFGBlock  = CFCtx.getCFG().getEntry();
+  const CFGBlock  = CFG.getEntry();

ymand wrote:

it was originally part of this patch, but I ended up undoing some of the new 
changes. I considered separating this out, but I think for such small NFC 
changes you run the real risk that you simply won't follow up. That is, it's a 
great idea, but if we try to make this the norm, I think the result will be 
many lost small cleanup opportunities. Maybe that's worth it, for review 
clarity. I don't really know where to draw the line.

https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-16 Thread via cfe-commits 


@@ -913,6 +913,34 @@ TEST_F(FlowConditionTest, WhileStmt) {
   });
 }
 
+TEST_F(FlowConditionTest, WhileStmtWithAssignmentInCondition) {
+  std::string Code = R"(
+void target(bool Foo) {
+  // This test checks whether the analysis preserves the connection between
+  // the value of `Foo` and the assignment expression, despite widening.
+  // The equality operator generates a fresh boolean variable on each
+  // interpretation, which forces use of widening.
+  while ((Foo = (3 == 4))) {
+(void)0;
+/*[[p]]*/
+  }
+}
+  )";
+  runDataflow(
+  Code,
+  [](const llvm::StringMap> ,
+ ASTContext ) {
+const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+ASSERT_THAT(FooDecl, NotNull());
+
+ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));

martinboehme wrote:

Suggest deleting this assertion. `getEnvironmentAtAnnotation()` already asserts 
that an annotation "p" exists.

(I know we assert this in a lot of existing tests, but it just seems like 
clutter.)

https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-16 Thread via cfe-commits 


@@ -913,6 +913,34 @@ TEST_F(FlowConditionTest, WhileStmt) {
   });
 }
 
+TEST_F(FlowConditionTest, WhileStmtWithAssignmentInCondition) {
+  std::string Code = R"(
+void target(bool Foo) {
+  // This test checks whether the analysis preserves the connection between
+  // the value of `Foo` and the assignment expression, despite widening.
+  // The equality operator generates a fresh boolean variable on each
+  // interpretation, which forces use of widening.
+  while ((Foo = (3 == 4))) {
+(void)0;
+/*[[p]]*/
+  }
+}
+  )";
+  runDataflow(
+  Code,
+  [](const llvm::StringMap> ,
+ ASTContext ) {
+const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+ASSERT_THAT(FooDecl, NotNull());

martinboehme wrote:

This assertion is unnecessary -- findValueDecl() already asserts internally 
that its return value is non-null. (But see also suggested edit below.)

https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-16 Thread via cfe-commits 


@@ -4099,6 +4099,20 @@ TEST(TransferTest, 
LoopDereferencingChangingRecordPointerConverges) {
   ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
 }
 
+TEST(TransferTest, LoopWithDisjunctiveConditionConverges) {

martinboehme wrote:

Test naming: I think the key aspect is not that the condition is a disjunction 
but that it's a short-circuited binary operator -- so maybe 
`LoopWithShortCircuitedConditionConverges`?

https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-16 Thread via cfe-commits 


@@ -53,19 +52,8 @@ static int blockIndexInPredecessor(const CFGBlock ,
   return BlockPos - Pred.succ_begin();
 }
 
-static bool isLoopHead(const CFGBlock ) {
-  if (const auto *T = B.getTerminatorStmt())
-switch (T->getStmtClass()) {
-  case Stmt::WhileStmtClass:
-  case Stmt::DoStmtClass:
-  case Stmt::ForStmtClass:
-  case Stmt::CXXForRangeStmtClass:
-return true;
-  default:
-return false;
-}
-
-  return false;
+static bool isBackedgeNode(const CFGBlock ) {

martinboehme wrote:

Can you add a short comment explaining what a "backedge node" is?

(I think the term "backedge node" isn't otherwise defined in Clang or the 
framework -- or if it is, it would be useful to add a link.)

https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-16 Thread via cfe-commits 


@@ -913,6 +913,34 @@ TEST_F(FlowConditionTest, WhileStmt) {
   });
 }
 
+TEST_F(FlowConditionTest, WhileStmtWithAssignmentInCondition) {
+  std::string Code = R"(
+void target(bool Foo) {
+  // This test checks whether the analysis preserves the connection between
+  // the value of `Foo` and the assignment expression, despite widening.
+  // The equality operator generates a fresh boolean variable on each
+  // interpretation, which forces use of widening.
+  while ((Foo = (3 == 4))) {
+(void)0;
+/*[[p]]*/
+  }
+}
+  )";
+  runDataflow(
+  Code,
+  [](const llvm::StringMap> ,
+ ASTContext ) {
+const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+ASSERT_THAT(FooDecl, NotNull());
+
+ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
+const Environment  = getEnvironmentAtAnnotation(Results, "p");
+
+auto  = cast(Env.getValue(*FooDecl))->formula();

martinboehme wrote:

```suggestion
const Environment  = getEnvironmentAtAnnotation(Results, "p");
auto  = getValueForDecl(ASTCtx, Env, "Foo");
```

You may need to include "TestingSupport.h".

https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-16 Thread via cfe-commits 


@@ -502,14 +490,15 @@ runTypeErasedDataflowAnalysis(
 PostVisitCFG) {
   PrettyStackTraceAnalysis CrashInfo(CFCtx, "runTypeErasedDataflowAnalysis");
 
-  PostOrderCFGView POV(());
-  ForwardDataflowWorklist Worklist(CFCtx.getCFG(), );
+  const clang::CFG  = CFCtx.getCFG();
+  PostOrderCFGView POV();
+  ForwardDataflowWorklist Worklist(CFG, );
 
   std::vector> BlockStates(
-  CFCtx.getCFG().size());
+  CFG.size());
 
   // The entry basic block doesn't contain statements so it can be skipped.
-  const CFGBlock  = CFCtx.getCFG().getEntry();
+  const CFGBlock  = CFG.getEntry();

martinboehme wrote:

Nit: This refactoring is entirely independent of the rest of this PR. Suggest 
submitting changes like this as a separate "NFC" PR to minimize the size of PRs 
and ease review.

https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-16 Thread via cfe-commits 

https://github.com/martinboehme edited 
https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-16 Thread via cfe-commits 

https://github.com/martinboehme approved this pull request.

LGTM with comments

https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-12 Thread Yitzhak Mandelbaum via cfe-commits 

ymand wrote:

> Nice fix! So, it looks like our definition of "loop head" was wrong.

Indeed. We didn't think of the way control-flow constructs *inside* the 
condition expression would be represented. Ironically (?), this is actually 
simpler and fixes another issue besides, which is nice. ;)

https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-12 Thread Yitzhak Mandelbaum via cfe-commits 

https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/68923

>From 83486a35e6d0e754dd99369fc546d04afedbe923 Mon Sep 17 00:00:00 2001
From: Yitzhak Mandelbaum 
Date: Thu, 12 Oct 2023 19:35:54 +
Subject: [PATCH 1/2] [clang][dataflow] Check for backedges directly (instead
 of loop statements).

Widen on backedge nodes, instead of nodes with a loop statement as terminator.
This fixes #67834 and a precision loss from assignment in a loop condition. The
commit contains tests for both of these issues.
---
 .../TypeErasedDataflowAnalysis.cpp| 29 ++-
 .../Analysis/FlowSensitive/TransferTest.cpp   | 14 +
 .../TypeErasedDataflowAnalysisTest.cpp| 28 ++
 3 files changed, 51 insertions(+), 20 deletions(-)

diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp 
b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
index 6b167891c1a3ac8..5da3a5b1ccf8a2c 100644
--- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -12,7 +12,6 @@
 
//===--===//
 
 #include 
-#include 
 #include 
 #include 
 #include 
@@ -33,8 +32,8 @@
 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallBitVector.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 
@@ -53,19 +52,8 @@ static int blockIndexInPredecessor(const CFGBlock ,
   return BlockPos - Pred.succ_begin();
 }
 
-static bool isLoopHead(const CFGBlock ) {
-  if (const auto *T = B.getTerminatorStmt())
-switch (T->getStmtClass()) {
-  case Stmt::WhileStmtClass:
-  case Stmt::DoStmtClass:
-  case Stmt::ForStmtClass:
-  case Stmt::CXXForRangeStmtClass:
-return true;
-  default:
-return false;
-}
-
-  return false;
+static bool isBackedgeNode(const CFGBlock ) {
+ return B.getLoopTarget() != nullptr;
 }
 
 namespace {
@@ -502,14 +490,15 @@ runTypeErasedDataflowAnalysis(
 PostVisitCFG) {
   PrettyStackTraceAnalysis CrashInfo(CFCtx, "runTypeErasedDataflowAnalysis");
 
-  PostOrderCFGView POV(());
-  ForwardDataflowWorklist Worklist(CFCtx.getCFG(), );
+  const clang::CFG  = CFCtx.getCFG();
+  PostOrderCFGView POV();
+  ForwardDataflowWorklist Worklist(CFG, );
 
   std::vector> BlockStates(
-  CFCtx.getCFG().size());
+  CFG.size());
 
   // The entry basic block doesn't contain statements so it can be skipped.
-  const CFGBlock  = CFCtx.getCFG().getEntry();
+  const CFGBlock  = CFG.getEntry();
   BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
  InitEnv.fork()};
   Worklist.enqueueSuccessors();
@@ -553,7 +542,7 @@ runTypeErasedDataflowAnalysis(
 llvm::errs() << "Old Env:\n";
 OldBlockState->Env.dump();
   });
-  if (isLoopHead(*Block)) {
+  if (isBackedgeNode(*Block)) {
 LatticeJoinEffect Effect1 = Analysis.widenTypeErased(
 NewBlockState.Lattice, OldBlockState->Lattice);
 LatticeJoinEffect Effect2 =
diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp 
b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
index 632632a1b30e78b..7c697fa5f87d941 100644
--- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
@@ -4099,6 +4099,20 @@ TEST(TransferTest, 
LoopDereferencingChangingRecordPointerConverges) {
   ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
 }
 
+TEST(TransferTest, LoopWithDisjunctiveConditionConverges) {
+  std::string Code = R"cc(
+bool foo();
+
+void target() {
+  bool c = false;
+  while (foo() || foo()) {
+c = true;
+  }
+}
+  )cc";
+  ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
+}
+
 TEST(TransferTest, DoesNotCrashOnUnionThisExpr) {
   std::string Code = R"(
 union Union {
diff --git 
a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp 
b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
index 2425bb8711bdbaf..6800d736afd9b08 100644
--- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
@@ -913,6 +913,34 @@ TEST_F(FlowConditionTest, WhileStmt) {
   });
 }
 
+TEST_F(FlowConditionTest, WhileStmtWithAssignmentInCondition) {
+  std::string Code = R"(
+void target(bool Foo) {
+  // This test checks whether the analysis preserves the connection between
+  // the value of `Foo` and the assignment expression, despite widening.
+  // The equality operator generates a fresh boolean variable on each
+

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-12 Thread Gábor Horváth via cfe-commits 

https://github.com/Xazax-hun approved this pull request.

Nice fix! So, it looks like our definition of "loop head" was wrong. 

https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-12 Thread via cfe-commits 

github-actions[bot] wrote:




:warning: C/C++ code formatter, clang-format found issues in your code. 
:warning:



You can test this locally with the following command:


``bash
git-clang-format --diff 50ece4cba949787241b5fbfc94be6cfdc66e90ee 
da8cacb47b8f80f7ecb1e86f98683be6c54b4e57 -- 
clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp 
clang/unittests/Analysis/FlowSensitive/TransferTest.cpp 
clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
``





View the diff from clang-format here.


``diff
diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp 
b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
index c635edd12219..d96ad66dd674 100644
--- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -53,7 +53,7 @@ static int blockIndexInPredecessor(const CFGBlock ,
 }
 
 static bool isBackedgeNode(const CFGBlock ) {
- return B.getLoopTarget() != nullptr;
+  return B.getLoopTarget() != nullptr;
 }
 
 namespace {
@@ -494,7 +494,6 @@ runTypeErasedDataflowAnalysis(
   PostOrderCFGView POV();
   ForwardDataflowWorklist Worklist(CFG, );
 
-
   std::vector> BlockStates(
   CFG.size());
 

``




https://github.com/llvm/llvm-project/pull/68923
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-12 Thread Yitzhak Mandelbaum via cfe-commits 

https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/68923

>From 83486a35e6d0e754dd99369fc546d04afedbe923 Mon Sep 17 00:00:00 2001
From: Yitzhak Mandelbaum 
Date: Thu, 12 Oct 2023 19:35:54 +
Subject: [PATCH] [clang][dataflow] Check for backedges directly (instead of
 loop statements).

Widen on backedge nodes, instead of nodes with a loop statement as terminator.
This fixes #67834 and a precision loss from assignment in a loop condition. The
commit contains tests for both of these issues.
---
 .../TypeErasedDataflowAnalysis.cpp| 29 ++-
 .../Analysis/FlowSensitive/TransferTest.cpp   | 14 +
 .../TypeErasedDataflowAnalysisTest.cpp| 28 ++
 3 files changed, 51 insertions(+), 20 deletions(-)

diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp 
b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
index 6b167891c1a3ac8..5da3a5b1ccf8a2c 100644
--- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -12,7 +12,6 @@
 
//===--===//
 
 #include 
-#include 
 #include 
 #include 
 #include 
@@ -33,8 +32,8 @@
 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallBitVector.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 
@@ -53,19 +52,8 @@ static int blockIndexInPredecessor(const CFGBlock ,
   return BlockPos - Pred.succ_begin();
 }
 
-static bool isLoopHead(const CFGBlock ) {
-  if (const auto *T = B.getTerminatorStmt())
-switch (T->getStmtClass()) {
-  case Stmt::WhileStmtClass:
-  case Stmt::DoStmtClass:
-  case Stmt::ForStmtClass:
-  case Stmt::CXXForRangeStmtClass:
-return true;
-  default:
-return false;
-}
-
-  return false;
+static bool isBackedgeNode(const CFGBlock ) {
+ return B.getLoopTarget() != nullptr;
 }
 
 namespace {
@@ -502,14 +490,15 @@ runTypeErasedDataflowAnalysis(
 PostVisitCFG) {
   PrettyStackTraceAnalysis CrashInfo(CFCtx, "runTypeErasedDataflowAnalysis");
 
-  PostOrderCFGView POV(());
-  ForwardDataflowWorklist Worklist(CFCtx.getCFG(), );
+  const clang::CFG  = CFCtx.getCFG();
+  PostOrderCFGView POV();
+  ForwardDataflowWorklist Worklist(CFG, );
 
   std::vector> BlockStates(
-  CFCtx.getCFG().size());
+  CFG.size());
 
   // The entry basic block doesn't contain statements so it can be skipped.
-  const CFGBlock  = CFCtx.getCFG().getEntry();
+  const CFGBlock  = CFG.getEntry();
   BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
  InitEnv.fork()};
   Worklist.enqueueSuccessors();
@@ -553,7 +542,7 @@ runTypeErasedDataflowAnalysis(
 llvm::errs() << "Old Env:\n";
 OldBlockState->Env.dump();
   });
-  if (isLoopHead(*Block)) {
+  if (isBackedgeNode(*Block)) {
 LatticeJoinEffect Effect1 = Analysis.widenTypeErased(
 NewBlockState.Lattice, OldBlockState->Lattice);
 LatticeJoinEffect Effect2 =
diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp 
b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
index 632632a1b30e78b..7c697fa5f87d941 100644
--- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
@@ -4099,6 +4099,20 @@ TEST(TransferTest, 
LoopDereferencingChangingRecordPointerConverges) {
   ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
 }
 
+TEST(TransferTest, LoopWithDisjunctiveConditionConverges) {
+  std::string Code = R"cc(
+bool foo();
+
+void target() {
+  bool c = false;
+  while (foo() || foo()) {
+c = true;
+  }
+}
+  )cc";
+  ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
+}
+
 TEST(TransferTest, DoesNotCrashOnUnionThisExpr) {
   std::string Code = R"(
 union Union {
diff --git 
a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp 
b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
index 2425bb8711bdbaf..6800d736afd9b08 100644
--- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
@@ -913,6 +913,34 @@ TEST_F(FlowConditionTest, WhileStmt) {
   });
 }
 
+TEST_F(FlowConditionTest, WhileStmtWithAssignmentInCondition) {
+  std::string Code = R"(
+void target(bool Foo) {
+  // This test checks whether the analysis preserves the connection between
+  // the value of `Foo` and the assignment expression, despite widening.
+  // The equality operator generates a fresh boolean variable on each
+

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-12 Thread via cfe-commits 

llvmbot wrote:




@llvm/pr-subscribers-clang

Author: Yitzhak Mandelbaum (ymand)


Changes

Widen on backedge nodes, instead of nodes with a loop statement as terminator.
This fixes #67834 and a precision loss from assignment in a loop 
condition. The
commit contains tests for both of these issues.


---
Full diff: https://github.com/llvm/llvm-project/pull/68923.diff


3 Files Affected:

- (modified) clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp 
(+10-20) 
- (modified) clang/unittests/Analysis/FlowSensitive/TransferTest.cpp (+14) 
- (modified) 
clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp (+28) 


``diff
diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp 
b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
index 6b167891c1a3ac8..c635edd12219f0e 100644
--- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -12,7 +12,6 @@
 
//===--===//
 
 #include 
-#include 
 #include 
 #include 
 #include 
@@ -33,8 +32,8 @@
 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallBitVector.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 
@@ -53,19 +52,8 @@ static int blockIndexInPredecessor(const CFGBlock ,
   return BlockPos - Pred.succ_begin();
 }
 
-static bool isLoopHead(const CFGBlock ) {
-  if (const auto *T = B.getTerminatorStmt())
-switch (T->getStmtClass()) {
-  case Stmt::WhileStmtClass:
-  case Stmt::DoStmtClass:
-  case Stmt::ForStmtClass:
-  case Stmt::CXXForRangeStmtClass:
-return true;
-  default:
-return false;
-}
-
-  return false;
+static bool isBackedgeNode(const CFGBlock ) {
+ return B.getLoopTarget() != nullptr;
 }
 
 namespace {
@@ -502,14 +490,16 @@ runTypeErasedDataflowAnalysis(
 PostVisitCFG) {
   PrettyStackTraceAnalysis CrashInfo(CFCtx, "runTypeErasedDataflowAnalysis");
 
-  PostOrderCFGView POV(());
-  ForwardDataflowWorklist Worklist(CFCtx.getCFG(), );
+  const clang::CFG  = CFCtx.getCFG();
+  PostOrderCFGView POV();
+  ForwardDataflowWorklist Worklist(CFG, );
+
 
   std::vector> BlockStates(
-  CFCtx.getCFG().size());
+  CFG.size());
 
   // The entry basic block doesn't contain statements so it can be skipped.
-  const CFGBlock  = CFCtx.getCFG().getEntry();
+  const CFGBlock  = CFG.getEntry();
   BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
  InitEnv.fork()};
   Worklist.enqueueSuccessors();
@@ -553,7 +543,7 @@ runTypeErasedDataflowAnalysis(
 llvm::errs() << "Old Env:\n";
 OldBlockState->Env.dump();
   });
-  if (isLoopHead(*Block)) {
+  if (isBackedgeNode(*Block)) {
 LatticeJoinEffect Effect1 = Analysis.widenTypeErased(
 NewBlockState.Lattice, OldBlockState->Lattice);
 LatticeJoinEffect Effect2 =
diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp 
b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
index 632632a1b30e78b..7c697fa5f87d941 100644
--- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
@@ -4099,6 +4099,20 @@ TEST(TransferTest, 
LoopDereferencingChangingRecordPointerConverges) {
   ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
 }
 
+TEST(TransferTest, LoopWithDisjunctiveConditionConverges) {
+  std::string Code = R"cc(
+bool foo();
+
+void target() {
+  bool c = false;
+  while (foo() || foo()) {
+c = true;
+  }
+}
+  )cc";
+  ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
+}
+
 TEST(TransferTest, DoesNotCrashOnUnionThisExpr) {
   std::string Code = R"(
 union Union {
diff --git 
a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp 
b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
index 2425bb8711bdbaf..6800d736afd9b08 100644
--- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
@@ -913,6 +913,34 @@ TEST_F(FlowConditionTest, WhileStmt) {
   });
 }
 
+TEST_F(FlowConditionTest, WhileStmtWithAssignmentInCondition) {
+  std::string Code = R"(
+void target(bool Foo) {
+  // This test checks whether the analysis preserves the connection between
+  // the value of `Foo` and the assignment expression, despite widening.
+  // The equality operator generates a fresh boolean variable on each
+  // interpretation, which forces use of widening.
+  while ((Foo = (3 == 4))) {
+(void)0;
+

[clang] [clang][dataflow] Check for backedges directly (instead of loop statements). (PR #68923)

2023-10-12 Thread Yitzhak Mandelbaum via cfe-commits 

https://github.com/ymand created https://github.com/llvm/llvm-project/pull/68923

Widen on backedge nodes, instead of nodes with a loop statement as terminator.
This fixes #67834 and a precision loss from assignment in a loop condition. The
commit contains tests for both of these issues.


>From da8cacb47b8f80f7ecb1e86f98683be6c54b4e57 Mon Sep 17 00:00:00 2001
From: Yitzhak Mandelbaum 
Date: Thu, 12 Oct 2023 19:35:54 +
Subject: [PATCH] [clang][dataflow] Check for backedges directly (instead of
 loop statements).

Widen on backedge nodes, instead of nodes with a loop statement as terminator.
This fixes #67834 and a precision loss from assignment in a loop condition. The
commit contains tests for both of these issues.
---
 .../TypeErasedDataflowAnalysis.cpp| 30 +++
 .../Analysis/FlowSensitive/TransferTest.cpp   | 14 +
 .../TypeErasedDataflowAnalysisTest.cpp| 28 +
 3 files changed, 52 insertions(+), 20 deletions(-)

diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp 
b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
index 6b167891c1a3ac8..c635edd12219f0e 100644
--- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -12,7 +12,6 @@
 
//===--===//
 
 #include 
-#include 
 #include 
 #include 
 #include 
@@ -33,8 +32,8 @@
 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallBitVector.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 
@@ -53,19 +52,8 @@ static int blockIndexInPredecessor(const CFGBlock ,
   return BlockPos - Pred.succ_begin();
 }
 
-static bool isLoopHead(const CFGBlock ) {
-  if (const auto *T = B.getTerminatorStmt())
-switch (T->getStmtClass()) {
-  case Stmt::WhileStmtClass:
-  case Stmt::DoStmtClass:
-  case Stmt::ForStmtClass:
-  case Stmt::CXXForRangeStmtClass:
-return true;
-  default:
-return false;
-}
-
-  return false;
+static bool isBackedgeNode(const CFGBlock ) {
+ return B.getLoopTarget() != nullptr;
 }
 
 namespace {
@@ -502,14 +490,16 @@ runTypeErasedDataflowAnalysis(
 PostVisitCFG) {
   PrettyStackTraceAnalysis CrashInfo(CFCtx, "runTypeErasedDataflowAnalysis");
 
-  PostOrderCFGView POV(());
-  ForwardDataflowWorklist Worklist(CFCtx.getCFG(), );
+  const clang::CFG  = CFCtx.getCFG();
+  PostOrderCFGView POV();
+  ForwardDataflowWorklist Worklist(CFG, );
+
 
   std::vector> BlockStates(
-  CFCtx.getCFG().size());
+  CFG.size());
 
   // The entry basic block doesn't contain statements so it can be skipped.
-  const CFGBlock  = CFCtx.getCFG().getEntry();
+  const CFGBlock  = CFG.getEntry();
   BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
  InitEnv.fork()};
   Worklist.enqueueSuccessors();
@@ -553,7 +543,7 @@ runTypeErasedDataflowAnalysis(
 llvm::errs() << "Old Env:\n";
 OldBlockState->Env.dump();
   });
-  if (isLoopHead(*Block)) {
+  if (isBackedgeNode(*Block)) {
 LatticeJoinEffect Effect1 = Analysis.widenTypeErased(
 NewBlockState.Lattice, OldBlockState->Lattice);
 LatticeJoinEffect Effect2 =
diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp 
b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
index 632632a1b30e78b..7c697fa5f87d941 100644
--- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
@@ -4099,6 +4099,20 @@ TEST(TransferTest, 
LoopDereferencingChangingRecordPointerConverges) {
   ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
 }
 
+TEST(TransferTest, LoopWithDisjunctiveConditionConverges) {
+  std::string Code = R"cc(
+bool foo();
+
+void target() {
+  bool c = false;
+  while (foo() || foo()) {
+c = true;
+  }
+}
+  )cc";
+  ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
+}
+
 TEST(TransferTest, DoesNotCrashOnUnionThisExpr) {
   std::string Code = R"(
 union Union {
diff --git 
a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp 
b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
index 2425bb8711bdbaf..6800d736afd9b08 100644
--- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
@@ -913,6 +913,34 @@ TEST_F(FlowConditionTest, WhileStmt) {
   });
 }
 
+TEST_F(FlowConditionTest, WhileStmtWithAssignmentInCondition) {
+  std::string Code = R"(
+void target(bool Foo) {
+  // This test checks