[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Gábor Horváth via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rG05c7dc664809: [DataFlow] Factor two worklist implementations 
out (authored by xazax.hun).

Changed prior to commit:
  https://reviews.llvm.org/D72380?vs=238592=238785#toc

Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380

Files:
  clang/include/clang/Analysis/FlowSensitive/DataflowValues.h
  clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h
  clang/lib/Analysis/LiveVariables.cpp
  clang/lib/Analysis/UninitializedValues.cpp
  clang/unittests/Analysis/CFGBuildResult.h
  clang/unittests/Analysis/CFGTest.cpp

Index: clang/unittests/Analysis/CFGTest.cpp
===
--- clang/unittests/Analysis/CFGTest.cpp
+++ clang/unittests/Analysis/CFGTest.cpp
@@ -7,10 +7,14 @@
 //===--===//
 
 #include "CFGBuildResult.h"
+#include "clang/AST/Decl.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
 #include "clang/Tooling/Tooling.h"
 #include "gtest/gtest.h"
+#include 
 #include 
 #include 
 
@@ -73,14 +77,14 @@
 EXPECT_EQ(IsLinear, B.getCFG()->isLinear());
   };
 
-  expectLinear(true,  "void foo() {}");
-  expectLinear(true,  "void foo() { if (true) return; }");
-  expectLinear(true,  "void foo() { if constexpr (false); }");
+  expectLinear(true, "void foo() {}");
+  expectLinear(true, "void foo() { if (true) return; }");
+  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.
+  expectLinear(true, "void foo() { do {} while (false); }");
+  expectLinear(true, "void foo() { foo(); }"); // Recursion is not our problem.
 }
 
 TEST(CFG, ElementRefIterator) {
@@ -216,6 +220,54 @@
   EXPECT_EQ(++(CMainBlock->rref_begin()), CMainBlock->rref_begin() + 1);
 }
 
+TEST(CFG, Worklists) {
+  const char *Code = "int f(bool cond) {\n"
+ "  int a = 5;\n"
+ "  if (cond)\n"
+ "a += 1;\n"
+ "  return a;\n"
+ "}\n";
+  BuildResult B = BuildCFG(Code);
+  EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());
+  const FunctionDecl *Func = B.getFunc();
+  AnalysisDeclContext AC(nullptr, Func);
+  auto *CFG = AC.getCFG();
+
+  std::vector ReferenceOrder;
+  for (const auto *B : *AC.getAnalysis())
+ReferenceOrder.push_back(B);
+
+  {
+ForwardDataflowWorklist ForwardWorklist(*CFG, AC);
+for (const auto *B : *CFG)
+  ForwardWorklist.enqueueBlock(B);
+
+std::vector ForwardNodes;
+while (const CFGBlock *B = ForwardWorklist.dequeue())
+  ForwardNodes.push_back(B);
+
+EXPECT_EQ(ForwardNodes.size(), ReferenceOrder.size());
+EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(),
+   ForwardNodes.begin()));
+  }
+
+  std::reverse(ReferenceOrder.begin(), ReferenceOrder.end());
+
+  {
+BackwardDataflowWorklist BackwardWorklist(*CFG, AC);
+for (const auto *B : *CFG)
+  BackwardWorklist.enqueueBlock(B);
+
+std::vector BackwardNodes;
+while (const CFGBlock *B = BackwardWorklist.dequeue())
+  BackwardNodes.push_back(B);
+
+EXPECT_EQ(BackwardNodes.size(), ReferenceOrder.size());
+EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(),
+   BackwardNodes.begin()));
+  }
+}
+
 } // namespace
 } // namespace analysis
 } // namespace clang
Index: clang/unittests/Analysis/CFGBuildResult.h
===
--- clang/unittests/Analysis/CFGBuildResult.h
+++ clang/unittests/Analysis/CFGBuildResult.h
@@ -23,18 +23,21 @@
 BuiltCFG,
   };
 
-  BuildResult(Status S, std::unique_ptr Cfg = nullptr,
+  BuildResult(Status S, const FunctionDecl *Func = nullptr,
+  std::unique_ptr Cfg = nullptr,
   std::unique_ptr AST = nullptr)
-  : S(S), Cfg(std::move(Cfg)), AST(std::move(AST)) {}
+  : S(S), Cfg(std::move(Cfg)), AST(std::move(AST)), Func(Func) {}
 
   Status getStatus() const { return S; }
   CFG *getCFG() const { return Cfg.get(); }
   ASTUnit *getAST() const { return AST.get(); }
+  const FunctionDecl *getFunc() const { return Func; }
 
 private:
   Status S;
   std::unique_ptr Cfg;
   std::unique_ptr AST;
+  const FunctionDecl *Func;
 };
 
 class CFGCallback : public ast_matchers::MatchFinder::MatchCallback {
@@ -54,7 +57,8 @@
 Options.AddImplicitDtors = true;
 if 

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Dmitri Gribenko via Phabricator via cfe-commits]

gribozavr2 accepted this revision.
gribozavr2 added a comment.
This revision is now accepted and ready to land.

Thank you for factoring our this library!

I briefly read the UninitializedValues analysis and I also think that this 
change is a no-op.




Comment at: clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h:59
+
+/// A worklist implementation for forward data-flow analysis. The enqueued
+/// blocks will be dequeued in reverse post order. The worklist cannot contain

s/data-flow/dataflow/ I think.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun updated this revision to Diff 238592.
xazax.hun added a comment.

- Fix typo.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380

Files:
  clang/include/clang/Analysis/FlowSensitive/DataflowValues.h
  clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h
  clang/lib/Analysis/LiveVariables.cpp
  clang/lib/Analysis/UninitializedValues.cpp
  clang/unittests/Analysis/CFGBuildResult.h
  clang/unittests/Analysis/CFGTest.cpp

Index: clang/unittests/Analysis/CFGTest.cpp
===
--- clang/unittests/Analysis/CFGTest.cpp
+++ clang/unittests/Analysis/CFGTest.cpp
@@ -7,10 +7,14 @@
 //===--===//
 
 #include "CFGBuildResult.h"
+#include "clang/AST/Decl.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
 #include "clang/Tooling/Tooling.h"
 #include "gtest/gtest.h"
+#include 
 #include 
 #include 
 
@@ -73,14 +77,14 @@
 EXPECT_EQ(IsLinear, B.getCFG()->isLinear());
   };
 
-  expectLinear(true,  "void foo() {}");
-  expectLinear(true,  "void foo() { if (true) return; }");
-  expectLinear(true,  "void foo() { if constexpr (false); }");
+  expectLinear(true, "void foo() {}");
+  expectLinear(true, "void foo() { if (true) return; }");
+  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.
+  expectLinear(true, "void foo() { do {} while (false); }");
+  expectLinear(true, "void foo() { foo(); }"); // Recursion is not our problem.
 }
 
 TEST(CFG, ElementRefIterator) {
@@ -216,6 +220,54 @@
   EXPECT_EQ(++(CMainBlock->rref_begin()), CMainBlock->rref_begin() + 1);
 }
 
+TEST(CFG, Worklists) {
+  const char *Code = "int f(bool cond) {\n"
+ "  int a = 5;\n"
+ "  if (cond)\n"
+ "a += 1;\n"
+ "  return a;\n"
+ "}\n";
+  BuildResult B = BuildCFG(Code);
+  EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());
+  const FunctionDecl *Func = B.getFunc();
+  AnalysisDeclContext AC(nullptr, Func);
+  auto *CFG = AC.getCFG();
+
+  std::vector ReferenceOrder;
+  for (const auto *B : *AC.getAnalysis())
+ReferenceOrder.push_back(B);
+
+  {
+ForwardDataflowWorklist ForwardWorklist(*CFG, AC);
+for (const auto *B : *CFG)
+  ForwardWorklist.enqueueBlock(B);
+
+std::vector ForwardNodes;
+while (const CFGBlock *B = ForwardWorklist.dequeue())
+  ForwardNodes.push_back(B);
+
+EXPECT_EQ(ForwardNodes.size(), ReferenceOrder.size());
+EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(),
+   ForwardNodes.begin()));
+  }
+
+  std::reverse(ReferenceOrder.begin(), ReferenceOrder.end());
+
+  {
+BackwardDataflowWorklist BackwardWorklist(*CFG, AC);
+for (const auto *B : *CFG)
+  BackwardWorklist.enqueueBlock(B);
+
+std::vector BackwardNodes;
+while (const CFGBlock *B = BackwardWorklist.dequeue())
+  BackwardNodes.push_back(B);
+
+EXPECT_EQ(BackwardNodes.size(), ReferenceOrder.size());
+EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(),
+   BackwardNodes.begin()));
+  }
+}
+
 } // namespace
 } // namespace analysis
 } // namespace clang
Index: clang/unittests/Analysis/CFGBuildResult.h
===
--- clang/unittests/Analysis/CFGBuildResult.h
+++ clang/unittests/Analysis/CFGBuildResult.h
@@ -23,18 +23,21 @@
 BuiltCFG,
   };
 
-  BuildResult(Status S, std::unique_ptr Cfg = nullptr,
+  BuildResult(Status S, const FunctionDecl *Func = nullptr,
+  std::unique_ptr Cfg = nullptr,
   std::unique_ptr AST = nullptr)
-  : S(S), Cfg(std::move(Cfg)), AST(std::move(AST)) {}
+  : S(S), Cfg(std::move(Cfg)), AST(std::move(AST)), Func(Func) {}
 
   Status getStatus() const { return S; }
   CFG *getCFG() const { return Cfg.get(); }
   ASTUnit *getAST() const { return AST.get(); }
+  const FunctionDecl *getFunc() const { return Func; }
 
 private:
   Status S;
   std::unique_ptr Cfg;
   std::unique_ptr AST;
+  const FunctionDecl *Func;
 };
 
 class CFGCallback : public ast_matchers::MatchFinder::MatchCallback {
@@ -54,7 +57,8 @@
 Options.AddImplicitDtors = true;
 if (std::unique_ptr Cfg =
 CFG::buildCFG(nullptr, Body, Result.Context, Options))
-  TheBuildResult = {BuildResult::BuiltCFG, std::move(Cfg), std::move(AST)};
+  TheBuildResult = 

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun added a comment.

Here is an example:

  void f() {
int i;
while (i < 42 && i) {
  if (i)

}
  }

This takes 17 visits before, 16 after.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun added a comment.

In D72380#1823019 , @xazax.hun wrote:

> In D72380#1822927 , @NoQ wrote:
>
> > The change in uninitialized values analysis gives me a bit of anxiety. 
> > Could you explain what exactly has changed that caused the change in the 
> > stats and why you think it doesn't make a difference, maybe give an 
> > example? (an example could be obtained by `creduce`-ing over "the stats 
> > have changed" criterion)
>
>
> We will process it multiple times with the original implementation, we 
> traverse the CFG both using DFS and using reverse post order.


Sorry, I just realized that the original code initially considers all the nodes 
queued. In this case there is no extra pass. But it is still true that the 
original is mostly using DFS while the new one is only using RPO. So it comes 
down to the order we visit the basic blocks. Working on a minimal repro.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun added a comment.

In D72380#1822927 , @NoQ wrote:

> The change in uninitialized values analysis gives me a bit of anxiety. Could 
> you explain what exactly has changed that caused the change in the stats and 
> why you think it doesn't make a difference, maybe give an example? (an 
> example could be obtained by `creduce`-ing over "the stats have changed" 
> criterion)


Yeah, this is the riskiest part, so I do understand the concerns. Basically, 
the former implementation was using `PostOrderCFGView::iterator`s and a stack 
(popping from the back of a smallvector). When the stack was empty, it popped 
the next element from the iterator. Also, the analysis queues the successors of 
a node once it was processed (and the analysis state was changed).
So let's imagine a linear CFG. We will process it multiple times with the 
original implementation, we traverse the CFG both using DFS and using reverse 
post order.

The new implementation is only using a reverse post order (no stack, no DFS), 
and does not have an extra pass over the CFG like the previous one.

Since this is a fixed point iteration and we should stop iterating whenever we 
reached the fixed point. Reaching that with fewer iterations sounds good to me. 
Since we always queue the successors of a changed node I have hard time 
imagining how could we stop prematurely.

I can look into a minimal repro if that helps.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added a comment.

I'm excited about this effort!~

The change in uninitialized values analysis gives me a bit of anxiety. Could 
you explain what exactly has changed that caused the change in the stats and 
why you think it doesn't make a difference, maybe give an example? (an example 
could be obtained by `creduce`-ing over "the stats have changed" criterion)


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun added a comment.

Ping for the other reviewers :)


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Matthias Gehre via Phabricator via cfe-commits]

mgehre added inline comments.



Comment at: clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h:20
+namespace clang {
+template  class DataflowWorklistBase {
+  llvm::BitVector EnqueuedBlocks;

xazax.hun wrote:
> xazax.hun wrote:
> > mgehre wrote:
> > > Should this class have a bit of doxygen and a unit test?
> > We have two users and both users have regression tests. More tests are 
> > always good, but I am not sure if we would get much value in this case. 
> > Having some comments sound very useful though :)
> Added a unit test anyway :)
;-)



Comment at: clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h:20
+namespace clang {
+/// A worklist implementation where the enqueued blocks wwill be dequeued based
+/// on the order defined by 'Comp'.

nit: wwill


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun updated this revision to Diff 236886.
xazax.hun added a comment.

- Added doxygen comments and unit tests.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380

Files:
  clang/include/clang/Analysis/FlowSensitive/DataflowValues.h
  clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h
  clang/lib/Analysis/LiveVariables.cpp
  clang/lib/Analysis/UninitializedValues.cpp
  clang/unittests/Analysis/CFGBuildResult.h
  clang/unittests/Analysis/CFGTest.cpp

Index: clang/unittests/Analysis/CFGTest.cpp
===
--- clang/unittests/Analysis/CFGTest.cpp
+++ clang/unittests/Analysis/CFGTest.cpp
@@ -7,10 +7,14 @@
 //===--===//
 
 #include "CFGBuildResult.h"
+#include "clang/AST/Decl.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
 #include "clang/Tooling/Tooling.h"
 #include "gtest/gtest.h"
+#include 
 #include 
 #include 
 
@@ -73,14 +77,14 @@
 EXPECT_EQ(IsLinear, B.getCFG()->isLinear());
   };
 
-  expectLinear(true,  "void foo() {}");
-  expectLinear(true,  "void foo() { if (true) return; }");
-  expectLinear(true,  "void foo() { if constexpr (false); }");
+  expectLinear(true, "void foo() {}");
+  expectLinear(true, "void foo() { if (true) return; }");
+  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.
+  expectLinear(true, "void foo() { do {} while (false); }");
+  expectLinear(true, "void foo() { foo(); }"); // Recursion is not our problem.
 }
 
 TEST(CFG, ElementRefIterator) {
@@ -216,6 +220,54 @@
   EXPECT_EQ(++(CMainBlock->rref_begin()), CMainBlock->rref_begin() + 1);
 }
 
+TEST(CFG, Worklists) {
+  const char *Code = "int f(bool cond) {\n"
+ "  int a = 5;\n"
+ "  if (cond)\n"
+ "a += 1;\n"
+ "  return a;\n"
+ "}\n";
+  BuildResult B = BuildCFG(Code);
+  EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());
+  const FunctionDecl *Func = B.getFunc();
+  AnalysisDeclContext AC(nullptr, Func);
+  auto *CFG = AC.getCFG();
+
+  std::vector ReferenceOrder;
+  for (const auto *B : *AC.getAnalysis())
+ReferenceOrder.push_back(B);
+
+  {
+ForwardDataflowWorklist ForwardWorklist(*CFG, AC);
+for (const auto *B : *CFG)
+  ForwardWorklist.enqueueBlock(B);
+
+std::vector ForwardNodes;
+while (const CFGBlock *B = ForwardWorklist.dequeue())
+  ForwardNodes.push_back(B);
+
+EXPECT_EQ(ForwardNodes.size(), ReferenceOrder.size());
+EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(),
+   ForwardNodes.begin()));
+  }
+
+  std::reverse(ReferenceOrder.begin(), ReferenceOrder.end());
+
+  {
+BackwardDataflowWorklist BackwardWorklist(*CFG, AC);
+for (const auto *B : *CFG)
+  BackwardWorklist.enqueueBlock(B);
+
+std::vector BackwardNodes;
+while (const CFGBlock *B = BackwardWorklist.dequeue())
+  BackwardNodes.push_back(B);
+
+EXPECT_EQ(BackwardNodes.size(), ReferenceOrder.size());
+EXPECT_TRUE(std::equal(ReferenceOrder.begin(), ReferenceOrder.end(),
+   BackwardNodes.begin()));
+  }
+}
+
 } // namespace
 } // namespace analysis
 } // namespace clang
Index: clang/unittests/Analysis/CFGBuildResult.h
===
--- clang/unittests/Analysis/CFGBuildResult.h
+++ clang/unittests/Analysis/CFGBuildResult.h
@@ -23,18 +23,21 @@
 BuiltCFG,
   };
 
-  BuildResult(Status S, std::unique_ptr Cfg = nullptr,
+  BuildResult(Status S, const FunctionDecl *Func = nullptr,
+  std::unique_ptr Cfg = nullptr,
   std::unique_ptr AST = nullptr)
-  : S(S), Cfg(std::move(Cfg)), AST(std::move(AST)) {}
+  : S(S), Cfg(std::move(Cfg)), AST(std::move(AST)), Func(Func) {}
 
   Status getStatus() const { return S; }
   CFG *getCFG() const { return Cfg.get(); }
   ASTUnit *getAST() const { return AST.get(); }
+  const FunctionDecl *getFunc() const { return Func; }
 
 private:
   Status S;
   std::unique_ptr Cfg;
   std::unique_ptr AST;
+  const FunctionDecl *Func;
 };
 
 class CFGCallback : public ast_matchers::MatchFinder::MatchCallback {
@@ -54,7 +57,8 @@
 Options.AddImplicitDtors = true;
 if (std::unique_ptr Cfg =
 CFG::buildCFG(nullptr, Body, Result.Context, Options))
-  TheBuildResult = {BuildResult::BuiltCFG, std::move(Cfg), std::move(AST)};
+  

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun marked 2 inline comments as done.
xazax.hun added inline comments.



Comment at: clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h:20
+namespace clang {
+template  class DataflowWorklistBase {
+  llvm::BitVector EnqueuedBlocks;

xazax.hun wrote:
> mgehre wrote:
> > Should this class have a bit of doxygen and a unit test?
> We have two users and both users have regression tests. More tests are always 
> good, but I am not sure if we would get much value in this case. Having some 
> comments sound very useful though :)
Added a unit test anyway :)


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun marked an inline comment as done.
xazax.hun added inline comments.



Comment at: clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h:20
+namespace clang {
+template  class DataflowWorklistBase {
+  llvm::BitVector EnqueuedBlocks;

mgehre wrote:
> Should this class have a bit of doxygen and a unit test?
We have two users and both users have regression tests. More tests are always 
good, but I am not sure if we would get much value in this case. Having some 
comments sound very useful though :)


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Matthias Gehre via Phabricator via cfe-commits]

mgehre added inline comments.



Comment at: clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h:20
+namespace clang {
+template  class DataflowWorklistBase {
+  llvm::BitVector EnqueuedBlocks;

Should this class have a bit of doxygen and a unit test?


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun added a comment.

Fortunately, UninitializedValues has some statistics. So I printed it for a big 
translation unit (SemaExpr.cpp) before and after this change.

Before:

  *** Analysis Based Warnings Stats:
  33023 functions analyzed (0 w/o CFGs).
161696 CFG blocks built.
4 average CFG blocks per function.
1246 max CFG blocks per function.
  4792 functions analyzed for uninitialiazed variables
9189 variables analyzed.
1 average variables per function.
55 max variables per function.
47089 block visits.
9 average block visits per function.
1039 max block visits per function.

After:

  *** Analysis Based Warnings Stats:
  33023 functions analyzed (0 w/o CFGs).
161696 CFG blocks built.
4 average CFG blocks per function.
1246 max CFG blocks per function.
  4792 functions analyzed for uninitialiazed variables
9189 variables analyzed.
1 average variables per function.
55 max variables per function.
45728 block visits.
9 average block visits per function.
1039 max block visits per function.

It looks like after getting rid of prepopulating the worklist we overall visit 
fewer blocks which sounds good. All the tests pass, so if those extra visits 
were necessary, we do not have test coverage for them. But this makes me think 
that performance-wise this change should not be bad.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun updated this revision to Diff 236873.
xazax.hun added a comment.

- Prepopulating the worklist for UninitializedValues seems to be redundant.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380

Files:
  clang/include/clang/Analysis/FlowSensitive/DataflowValues.h
  clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h
  clang/lib/Analysis/LiveVariables.cpp
  clang/lib/Analysis/UninitializedValues.cpp

Index: clang/lib/Analysis/UninitializedValues.cpp
===
--- clang/lib/Analysis/UninitializedValues.cpp
+++ clang/lib/Analysis/UninitializedValues.cpp
@@ -24,6 +24,7 @@
 #include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/DomainSpecific/ObjCNoReturn.h"
+#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
 #include "clang/Basic/LLVM.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
@@ -212,68 +213,6 @@
   return scratch[idx.getValue()];
 }
 
-////
-// Worklist: worklist for dataflow analysis.
-////
-
-namespace {
-
-class DataflowWorklist {
-  PostOrderCFGView::iterator PO_I, PO_E;
-  SmallVector worklist;
-  llvm::BitVector enqueuedBlocks;
-
-public:
-  DataflowWorklist(const CFG , PostOrderCFGView )
-  : PO_I(view.begin()), PO_E(view.end()),
-enqueuedBlocks(cfg.getNumBlockIDs(), true) {
-// Treat the first block as already analyzed.
-if (PO_I != PO_E) {
-  assert(*PO_I == ());
-  enqueuedBlocks[(*PO_I)->getBlockID()] = false;
-  ++PO_I;
-}
-  }
-
-  void enqueueSuccessors(const CFGBlock *block);
-  const CFGBlock *dequeue();
-};
-
-} // namespace
-
-void DataflowWorklist::enqueueSuccessors(const CFGBlock *block) {
-  for (CFGBlock::const_succ_iterator I = block->succ_begin(),
-   E = block->succ_end(); I != E; ++I) {
-const CFGBlock *Successor = *I;
-if (!Successor || enqueuedBlocks[Successor->getBlockID()])
-  continue;
-worklist.push_back(Successor);
-enqueuedBlocks[Successor->getBlockID()] = true;
-  }
-}
-
-const CFGBlock *DataflowWorklist::dequeue() {
-  const CFGBlock *B = nullptr;
-
-  // First dequeue from the worklist.  This can represent
-  // updates along backedges that we want propagated as quickly as possible.
-  if (!worklist.empty())
-B = worklist.pop_back_val();
-
-  // Next dequeue from the initial reverse post order.  This is the
-  // theoretical ideal in the presence of no back edges.
-  else if (PO_I != PO_E) {
-B = *PO_I;
-++PO_I;
-  }
-  else
-return nullptr;
-
-  assert(enqueuedBlocks[B->getBlockID()] == true);
-  enqueuedBlocks[B->getBlockID()] = false;
-  return B;
-}
-
 ////
 // Classification of DeclRefExprs as use or initialization.
 ////
@@ -924,7 +863,7 @@
   }
 
   // Proceed with the workist.
-  DataflowWorklist worklist(cfg, *ac.getAnalysis());
+  ForwardDataflowWorklist worklist(cfg, ac);
   llvm::BitVector previouslyVisited(cfg.getNumBlockIDs());
   worklist.enqueueSuccessors(());
   llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false);
Index: clang/lib/Analysis/LiveVariables.cpp
===
--- clang/lib/Analysis/LiveVariables.cpp
+++ clang/lib/Analysis/LiveVariables.cpp
@@ -13,63 +13,16 @@
 #include "clang/Analysis/Analyses/LiveVariables.h"
 #include "clang/AST/Stmt.h"
 #include "clang/AST/StmtVisitor.h"
-#include "clang/Analysis/Analyses/PostOrderCFGView.h"
 #include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/PostOrderIterator.h"
-#include "llvm/ADT/PriorityQueue.h"
 #include "llvm/Support/raw_ostream.h"
 #include 
 #include 
 
 using namespace clang;
 
-namespace {
-
-class DataflowWorklist {
-  llvm::BitVector enqueuedBlocks;
-  PostOrderCFGView *POV;
-  llvm::PriorityQueue,
-  PostOrderCFGView::BlockOrderCompare> worklist;
-
-public:
-  DataflowWorklist(const CFG , AnalysisDeclContext )
-: enqueuedBlocks(cfg.getNumBlockIDs()),
-  POV(Ctx.getAnalysis()),
-  worklist(POV->getComparator()) {}
-
-  void enqueueBlock(const CFGBlock *block);
-  void enqueuePredecessors(const CFGBlock *block);
-
-  const CFGBlock *dequeue();
-};
-
-}
-
-void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) {
-  if (block && !enqueuedBlocks[block->getBlockID()]) {
-enqueuedBlocks[block->getBlockID()] = true;
-worklist.push(block);
-  }
-}
-
-void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) {
-  for (CFGBlock::const_pred_iterator I = 

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun updated this revision to Diff 236734.
xazax.hun added a comment.

- Add missing new line at the end of file.
- Populate the initial worklist in UninitializedValues more efficiently.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72380/new/

https://reviews.llvm.org/D72380

Files:
  clang/include/clang/Analysis/FlowSensitive/DataflowValues.h
  clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h
  clang/lib/Analysis/LiveVariables.cpp
  clang/lib/Analysis/UninitializedValues.cpp

Index: clang/lib/Analysis/UninitializedValues.cpp
===
--- clang/lib/Analysis/UninitializedValues.cpp
+++ clang/lib/Analysis/UninitializedValues.cpp
@@ -24,6 +24,7 @@
 #include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/DomainSpecific/ObjCNoReturn.h"
+#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
 #include "clang/Basic/LLVM.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
@@ -212,68 +213,6 @@
   return scratch[idx.getValue()];
 }
 
-////
-// Worklist: worklist for dataflow analysis.
-////
-
-namespace {
-
-class DataflowWorklist {
-  PostOrderCFGView::iterator PO_I, PO_E;
-  SmallVector worklist;
-  llvm::BitVector enqueuedBlocks;
-
-public:
-  DataflowWorklist(const CFG , PostOrderCFGView )
-  : PO_I(view.begin()), PO_E(view.end()),
-enqueuedBlocks(cfg.getNumBlockIDs(), true) {
-// Treat the first block as already analyzed.
-if (PO_I != PO_E) {
-  assert(*PO_I == ());
-  enqueuedBlocks[(*PO_I)->getBlockID()] = false;
-  ++PO_I;
-}
-  }
-
-  void enqueueSuccessors(const CFGBlock *block);
-  const CFGBlock *dequeue();
-};
-
-} // namespace
-
-void DataflowWorklist::enqueueSuccessors(const CFGBlock *block) {
-  for (CFGBlock::const_succ_iterator I = block->succ_begin(),
-   E = block->succ_end(); I != E; ++I) {
-const CFGBlock *Successor = *I;
-if (!Successor || enqueuedBlocks[Successor->getBlockID()])
-  continue;
-worklist.push_back(Successor);
-enqueuedBlocks[Successor->getBlockID()] = true;
-  }
-}
-
-const CFGBlock *DataflowWorklist::dequeue() {
-  const CFGBlock *B = nullptr;
-
-  // First dequeue from the worklist.  This can represent
-  // updates along backedges that we want propagated as quickly as possible.
-  if (!worklist.empty())
-B = worklist.pop_back_val();
-
-  // Next dequeue from the initial reverse post order.  This is the
-  // theoretical ideal in the presence of no back edges.
-  else if (PO_I != PO_E) {
-B = *PO_I;
-++PO_I;
-  }
-  else
-return nullptr;
-
-  assert(enqueuedBlocks[B->getBlockID()] == true);
-  enqueuedBlocks[B->getBlockID()] = false;
-  return B;
-}
-
 ////
 // Classification of DeclRefExprs as use or initialization.
 ////
@@ -924,7 +863,15 @@
   }
 
   // Proceed with the workist.
-  DataflowWorklist worklist(cfg, *ac.getAnalysis());
+  ForwardDataflowWorklist worklist(cfg, ac);
+  // Populate the initial queue.
+  {
+auto it = worklist.getCFGView()->begin();
+auto end = worklist.getCFGView()->end();
+++it; // Treat start as analyzed.
+for (; it != end; ++it)
+   worklist.enqueueBlock(*it);
+  }
   llvm::BitVector previouslyVisited(cfg.getNumBlockIDs());
   worklist.enqueueSuccessors(());
   llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false);
Index: clang/lib/Analysis/LiveVariables.cpp
===
--- clang/lib/Analysis/LiveVariables.cpp
+++ clang/lib/Analysis/LiveVariables.cpp
@@ -13,63 +13,16 @@
 #include "clang/Analysis/Analyses/LiveVariables.h"
 #include "clang/AST/Stmt.h"
 #include "clang/AST/StmtVisitor.h"
-#include "clang/Analysis/Analyses/PostOrderCFGView.h"
 #include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/PostOrderIterator.h"
-#include "llvm/ADT/PriorityQueue.h"
 #include "llvm/Support/raw_ostream.h"
 #include 
 #include 
 
 using namespace clang;
 
-namespace {
-
-class DataflowWorklist {
-  llvm::BitVector enqueuedBlocks;
-  PostOrderCFGView *POV;
-  llvm::PriorityQueue,
-  PostOrderCFGView::BlockOrderCompare> worklist;
-
-public:
-  DataflowWorklist(const CFG , AnalysisDeclContext )
-: enqueuedBlocks(cfg.getNumBlockIDs()),
-  POV(Ctx.getAnalysis()),
-  worklist(POV->getComparator()) {}
-
-  void enqueueBlock(const CFGBlock *block);
-  void enqueuePredecessors(const CFGBlock *block);
-
-  const CFGBlock *dequeue();
-};
-
-}
-
-void DataflowWorklist::enqueueBlock(const 

[PATCH] D72380: [DataFlow] Factor two worklist implementations out

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun created this revision.
xazax.hun added reviewers: gribozavr2, NoQ, Szelethus, rsmith.
xazax.hun added a project: clang.
Herald added subscribers: Charusso, gamesh411, dkrupp, rnkovacs.

In Clang, we have the tendency to have ad-hoc worklist implementations 
everywhere. This patch is a first attempt to try to make two of them reusable. 
In case the flow-sensitive lifetime analysis gets upstreamed, it is also likely 
to use the FordwardDataflowWorklist type (it is already using something very 
similar). 
This could also be useful for future dataflow algorithms.

The UninitializedValues analysis used to do something slightly different which 
should functionally equivalent with the new implementation but might be 
slightly more efficient. To tell the truth, I did not measure the performance 
implications yet. 
Originally, it did not enqueue the whole CFG to initially populate the 
worklist. It maintained an iterator instead, and initially, the blocks were 
popped from the iterator instead of the queue.

Do we have a good benchmark to measure the differences? In case this code 
happens to be performance critical I could try to do some similar optimizations 
to the new version.

What do you think, is this something we should pursue?


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D72380

Files:
  clang/include/clang/Analysis/FlowSensitive/DataflowValues.h
  clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h
  clang/lib/Analysis/LiveVariables.cpp
  clang/lib/Analysis/UninitializedValues.cpp

Index: clang/lib/Analysis/UninitializedValues.cpp
===
--- clang/lib/Analysis/UninitializedValues.cpp
+++ clang/lib/Analysis/UninitializedValues.cpp
@@ -24,6 +24,7 @@
 #include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/DomainSpecific/ObjCNoReturn.h"
+#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
 #include "clang/Basic/LLVM.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
@@ -212,68 +213,6 @@
   return scratch[idx.getValue()];
 }
 
-////
-// Worklist: worklist for dataflow analysis.
-////
-
-namespace {
-
-class DataflowWorklist {
-  PostOrderCFGView::iterator PO_I, PO_E;
-  SmallVector worklist;
-  llvm::BitVector enqueuedBlocks;
-
-public:
-  DataflowWorklist(const CFG , PostOrderCFGView )
-  : PO_I(view.begin()), PO_E(view.end()),
-enqueuedBlocks(cfg.getNumBlockIDs(), true) {
-// Treat the first block as already analyzed.
-if (PO_I != PO_E) {
-  assert(*PO_I == ());
-  enqueuedBlocks[(*PO_I)->getBlockID()] = false;
-  ++PO_I;
-}
-  }
-
-  void enqueueSuccessors(const CFGBlock *block);
-  const CFGBlock *dequeue();
-};
-
-} // namespace
-
-void DataflowWorklist::enqueueSuccessors(const CFGBlock *block) {
-  for (CFGBlock::const_succ_iterator I = block->succ_begin(),
-   E = block->succ_end(); I != E; ++I) {
-const CFGBlock *Successor = *I;
-if (!Successor || enqueuedBlocks[Successor->getBlockID()])
-  continue;
-worklist.push_back(Successor);
-enqueuedBlocks[Successor->getBlockID()] = true;
-  }
-}
-
-const CFGBlock *DataflowWorklist::dequeue() {
-  const CFGBlock *B = nullptr;
-
-  // First dequeue from the worklist.  This can represent
-  // updates along backedges that we want propagated as quickly as possible.
-  if (!worklist.empty())
-B = worklist.pop_back_val();
-
-  // Next dequeue from the initial reverse post order.  This is the
-  // theoretical ideal in the presence of no back edges.
-  else if (PO_I != PO_E) {
-B = *PO_I;
-++PO_I;
-  }
-  else
-return nullptr;
-
-  assert(enqueuedBlocks[B->getBlockID()] == true);
-  enqueuedBlocks[B->getBlockID()] = false;
-  return B;
-}
-
 ////
 // Classification of DeclRefExprs as use or initialization.
 ////
@@ -924,7 +863,12 @@
   }
 
   // Proceed with the workist.
-  DataflowWorklist worklist(cfg, *ac.getAnalysis());
+  ForwardDataflowWorklist worklist(cfg, ac);
+  // Populate the initial queue, treat start as analyzed.
+  for (const auto *B : *ac.getAnalysis()) {
+if (B != ())
+  worklist.enqueueBlock(B);
+  }
   llvm::BitVector previouslyVisited(cfg.getNumBlockIDs());
   worklist.enqueueSuccessors(());
   llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false);
Index: clang/lib/Analysis/LiveVariables.cpp
===
--- clang/lib/Analysis/LiveVariables.cpp
+++ clang/lib/Analysis/LiveVariables.cpp
@@ -13,63 +13,16 @@
 #include "clang/Analysis/Analyses/LiveVariables.h"
 #include "clang/AST/Stmt.h"
 #include "clang/AST/StmtVisitor.h"
-#include