[DataFlow] Factor two worklist implementations out

[xazax.hun]

Summary

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 be functionally equivalent with the new implementation. To tell the truth, I did not measure the performance implications yet.
The number of visited blocks decreased after the change, so I assume the performance should not regress. The tests we have did not uncover any problems with decreased number of visits.

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

[xazax.hun]

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

[xazax.hun]

• Prepopulating the worklist for UninitializedValues seems to be redundant.

[xazax.hun]

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.

[mgehre]

clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h

21

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

[xazax.hun]

clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h

21

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 :)

[xazax.hun]

• Added doxygen comments and unit tests.

[xazax.hun]

clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h

21

Added a unit test anyway :)

[mgehre]

clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h

20

nit: wwill

21

;-)

[xazax.hun]

Ping for the other reviewers :)

[NoQ]

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)

[xazax.hun]

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::iterators 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.

[xazax.hun]

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.

[xazax.hun]

Here is an example:

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

This takes 17 visits before, 16 after.

[xazax.hun]

• Fix typo.

[gribozavr2]

Thank you for factoring our this library!

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

clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h

59

s/data-flow/dataflow/ I think.

clang/include/clang/Analysis/FlowSensitive/DataflowValues.h

 protected:
   EdgeDataMapTy      EdgeDataMap;
   BlockDataMapTy     BlockDataMap;
   StmtDataMapTy*     StmtDataMap;
   AnalysisDataTy     AnalysisData;
 };
 
 } // end namespace clang
-#endif
+#endif // LLVM_CLANG_ANALYSES_DATAFLOW_VALUES

clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h

+//===- DataflowWorklist.h ---------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// A simple and reusable worklist for flow-sensitive analyses.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H
+
+#include "clang/Analysis/Analyses/PostOrderCFGView.h"
+#include "clang/Analysis/CFG.h"
+#include "llvm/ADT/PriorityQueue.h"
+
+namespace clang {
+/// A worklist implementation where the enqueued blocks wwill be dequeued based
+/// on the order defined by 'Comp'.
+template <typename Comp, unsigned QueueSize> class DataflowWorklistBase {
+  llvm::BitVector EnqueuedBlocks;
+  PostOrderCFGView *POV;
+  llvm::PriorityQueue<const CFGBlock *,
+                      SmallVector<const CFGBlock *, QueueSize>, Comp>
+      WorkList;
+
+public:
+  DataflowWorklistBase(const CFG &Cfg, PostOrderCFGView *POV, Comp C)
+      : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}
+
+  const PostOrderCFGView *getCFGView() const { return POV; }
+
+  void enqueueBlock(const CFGBlock *Block) {
+    if (Block && !EnqueuedBlocks[Block->getBlockID()]) {
+      EnqueuedBlocks[Block->getBlockID()] = true;
+      WorkList.push(Block);
+    }
+  }
+
+  const CFGBlock *dequeue() {
+    if (WorkList.empty())
+      return nullptr;
+    const CFGBlock *B = WorkList.top();
+    WorkList.pop();
+    EnqueuedBlocks[B->getBlockID()] = false;
+    return B;
+  }
+};
+
+struct ReversePostOrderCompare {
+  PostOrderCFGView::BlockOrderCompare Cmp;
+  bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const {
+    return Cmp(rhs, lhs);
+  }
+};
+
+/// A worklist implementation for forward data-flow analysis. The enqueued
+/// blocks will be dequeued in reverse post order. The worklist cannot contain
+/// the same block multiple times at once.
+struct ForwardDataflowWorklist
+    : DataflowWorklistBase<ReversePostOrderCompare, 20> {
+  ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
+      : DataflowWorklistBase(
+            Cfg, Ctx.getAnalysis<PostOrderCFGView>(),
+            ReversePostOrderCompare{
+                Ctx.getAnalysis<PostOrderCFGView>()->getComparator()}) {}
+
+  void enqueueSuccessors(const CFGBlock *Block) {
+    for (auto B : Block->succs())
+      enqueueBlock(B);
+  }
+};
+
+/// A worklist implementation for backward data-flow analysis. The enqueued
+/// block will be dequeued in post order. The worklist cannot contain the same
+/// block multiple times at once.
+struct BackwardDataflowWorklist
+    : DataflowWorklistBase<PostOrderCFGView::BlockOrderCompare, 20> {
+  BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
+      : DataflowWorklistBase(
+            Cfg, Ctx.getAnalysis<PostOrderCFGView>(),
+            Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {}
+
+  void enqueuePredecessors(const CFGBlock *Block) {
+    for (auto B : Block->preds())
+      enqueueBlock(B);
+  }
+};
+
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H

clang/lib/Analysis/LiveVariables.cpp

 //=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements Live Variables analysis for source-level CFGs.
 //
 //===----------------------------------------------------------------------===//
 
 #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 <algorithm>
 #include <vector>
 
 using namespace clang;
 
 namespace {
-
-class DataflowWorklist {
-  llvm::BitVector enqueuedBlocks;
-  PostOrderCFGView *POV;
-  llvm::PriorityQueue<const CFGBlock *, SmallVector<const CFGBlock *, 20>,
-                      PostOrderCFGView::BlockOrderCompare> worklist;
-
-public:
-  DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx)
-    : enqueuedBlocks(cfg.getNumBlockIDs()),
-      POV(Ctx.getAnalysis<PostOrderCFGView>()),
-      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 = block->pred_begin(),
-       E = block->pred_end(); I != E; ++I) {
-    enqueueBlock(*I);
-  }
-}
-
-const CFGBlock *DataflowWorklist::dequeue() {
-  if (worklist.empty())
-    return nullptr;
-  const CFGBlock *b = worklist.top();
-  worklist.pop();
-  enqueuedBlocks[b->getBlockID()] = false;
-  return b;
-}
-
-namespace {
 class LiveVariablesImpl {
 public:
   AnalysisDeclContext &analysisContext;
   llvm::ImmutableSet<const Stmt *>::Factory SSetFact;
   llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
   llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact;
   llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
   llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
SET mergeSets(SET A, SET B) {
     if (A.isEmpty())
       return B;
 
     for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
       A = A.add(*it);
     }
     return A;
   }
-}
+} // namespace
 
 void LiveVariables::Observer::anchor() { }
 
 LiveVariables::LivenessValues
 LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
                          LiveVariables::LivenessValues valsB) {
 
   llvm::ImmutableSetRef<const Stmt *>
public:
   void VisitBlockExpr(BlockExpr *BE);
   void VisitDeclRefExpr(DeclRefExpr *DR);
   void VisitDeclStmt(DeclStmt *DS);
   void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);
   void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);
   void VisitUnaryOperator(UnaryOperator *UO);
   void Visit(Stmt *S);
 };
-}
+} // namespace
 
 static const VariableArrayType *FindVA(QualType Ty) {
   const Type *ty = Ty.getTypePtr();
   while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
     if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))
       if (VAT->getSizeExpr())
         return VAT;
 
LiveVariables::computeLiveness(AnalysisDeclContext &AC,
   // Bail out if it looks too large.
   if (cfg->getNumBlockIDs() > 300000)
     return nullptr;
 
   LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
 
   // Construct the dataflow worklist.  Enqueue the exit block as the
   // start of the analysis.
-  DataflowWorklist worklist(*cfg, AC);
+  BackwardDataflowWorklist worklist(*cfg, AC);
   llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
 
   // FIXME: we should enqueue using post order.
   for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
     const CFGBlock *block = *it;
     worklist.enqueueBlock(block);
 
     // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.

clang/lib/Analysis/UninitializedValues.cpp

 #include "clang/AST/Stmt.h"
 #include "clang/AST/StmtObjC.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/AST/Type.h"
 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
 #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"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PackedVector.h"
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/ADT/SmallVector.h"

 
 ValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) {
   const Optional<unsigned> &idx = declToIndex.getValueIndex(vd);
   assert(idx.hasValue());
   return scratch[idx.getValue()];
 }
 
 //------------------------------------------------------------------------====//
-// Worklist: worklist for dataflow analysis.
-//====------------------------------------------------------------------------//
-
-namespace {
-
-class DataflowWorklist {
-  PostOrderCFGView::iterator PO_I, PO_E;
-  SmallVector<const CFGBlock *, 20> worklist;
-  llvm::BitVector enqueuedBlocks;
-
-public:
-  DataflowWorklist(const CFG &cfg, PostOrderCFGView &view)
-      : 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 == &cfg.getEntry());
-      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.
 //====------------------------------------------------------------------------//
 
 namespace {
 
 class FindVarResult {
   const VarDecl *vd;
   const DeclRefExpr *dr;
void clang::runUninitializedVariablesAnalysis(
   const CFGBlock &entry = cfg.getEntry();
   ValueVector &vec = vals.getValueVector(&entry);
   const unsigned n = vals.getNumEntries();
   for (unsigned j = 0; j < n; ++j) {
     vec[j] = Uninitialized;
   }
 
   // Proceed with the workist.
-  DataflowWorklist worklist(cfg, *ac.getAnalysis<PostOrderCFGView>());
+  ForwardDataflowWorklist worklist(cfg, ac);
   llvm::BitVector previouslyVisited(cfg.getNumBlockIDs());
   worklist.enqueueSuccessors(&cfg.getEntry());
   llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false);
   wasAnalyzed[cfg.getEntry().getBlockID()] = true;
   PruneBlocksHandler PBH(cfg.getNumBlockIDs());
 
   while (const CFGBlock *block = worklist.dequeue()) {
     PBH.currentBlock = block->getBlockID();

clang/unittests/Analysis/CFGBuildResult.h

 public:
   enum Status {
     ToolFailed,
     ToolRan,
     SawFunctionBody,
     BuiltCFG,
   };
 
-  BuildResult(Status S, std::unique_ptr<CFG> Cfg = nullptr,
+  BuildResult(Status S, const FunctionDecl *Func = nullptr,
+              std::unique_ptr<CFG> Cfg = nullptr,
               std::unique_ptr<ASTUnit> 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> Cfg;
   std::unique_ptr<ASTUnit> AST;
+  const FunctionDecl *Func;
 };
 
 class CFGCallback : public ast_matchers::MatchFinder::MatchCallback {
 public:
   CFGCallback(std::unique_ptr<ASTUnit> AST) : AST(std::move(AST)) {}
 
   std::unique_ptr<ASTUnit> AST;
   BuildResult TheBuildResult = BuildResult::ToolRan;
   CFG::BuildOptions Options;
 
   void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
     const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
     Stmt *Body = Func->getBody();
     if (!Body)
       return;
     TheBuildResult = BuildResult::SawFunctionBody;
     Options.AddImplicitDtors = true;
     if (std::unique_ptr<CFG> Cfg =
             CFG::buildCFG(nullptr, Body, Result.Context, Options))
-      TheBuildResult = {BuildResult::BuiltCFG, std::move(Cfg), std::move(AST)};
+      TheBuildResult = {BuildResult::BuiltCFG, Func, std::move(Cfg),
+                        std::move(AST)};
   }
 };
 
 inline BuildResult BuildCFG(const char *Code, CFG::BuildOptions Options = {}) {
   std::vector<std::string> Args = {"-std=c++11",
                                    "-fno-delayed-template-parsing"};
   std::unique_ptr<ASTUnit> AST = tooling::buildASTFromCodeWithArgs(Code, Args);
   if (!AST)

clang/unittests/Analysis/CFGTest.cpp

 //===- unittests/Analysis/CFGTest.cpp - CFG tests -------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #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 <algorithm>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace analysis {
 namespace {
 
 // Constructing a CFG for a range-based for over a dependent type fails (but

 
 TEST(CFG, IsLinear) {
   auto expectLinear = [](bool IsLinear, const char *Code) {
     BuildResult B = BuildCFG(Code);
     EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());
     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) {
   const char *Code = R"(void f() {
                           int i;
                           int j;
                           i = 5;
                           i = 6;
TEST(CFG, ElementRefIterator) {
   EXPECT_EQ(CMainBlock->rref_end() - MainBlockSize - 1,
             CMainBlock->rref_begin());
   EXPECT_EQ(CMainBlock->rref_begin() + MainBlockSize + 1,
             CMainBlock->rref_end());
   EXPECT_EQ(CMainBlock->rref_begin()++, CMainBlock->rref_begin());
   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<const CFGBlock *> ReferenceOrder;
+  for (const auto *B : *AC.getAnalysis<PostOrderCFGView>())
+    ReferenceOrder.push_back(B);
+
+  {
+    ForwardDataflowWorklist ForwardWorklist(*CFG, AC);
+    for (const auto *B : *CFG)
+      ForwardWorklist.enqueueBlock(B);
+
+    std::vector<const CFGBlock *> 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<const CFGBlock *> 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