[clang][dataflow] Refactor `DataflowWorklist` types and add a WTO version.

[ymandel]

Summary

Removes dependency of the DataflowWorklistBase type on the PostOrderCFGView. The
base had no particular connection to this order -- looks like it was included as
a convenience to the two derived classes rather than because it belonged there
conceptually. Removing it cleans up the base class a bit and makes it suitable
to extension with the new WTODataflowWorklist class.

[ymandel]

rebase

[ymandel]

rebase onto main.

[xazax.hun]

Mea culpa. Looks like I did not anticipate non-RPO worklists. Thanks for cleaning this up, looks good to me!

[ymandel]

In D153071#4561993, @xazax.hun wrote:

Mea culpa. Looks like I did not anticipate non-RPO worklists. Thanks for cleaning this up, looks good to me!

Thanks! Not anticipating the future is pretty standard, no need to apologize. ;)

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/IntervalPartition.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 will 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; }
+  DataflowWorklistBase(const CFG &Cfg, Comp C)
+      : EnqueuedBlocks(Cfg.getNumBlockIDs()), WorkList(C) {}
 
   void enqueueBlock(const CFGBlock *Block) {
     if (Block && !EnqueuedBlocks[Block->getBlockID()]) {
       EnqueuedBlocks[Block->getBlockID()] = true;
       WorkList.push(Block);
     }
   }
 

 };
 
 /// A worklist implementation for forward dataflow 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, PostOrderCFGView *POV)
-      : DataflowWorklistBase(Cfg, POV,
+      : DataflowWorklistBase(Cfg,
                              ReversePostOrderCompare{POV->getComparator()}) {}
 
   ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
       : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {}
 
   void enqueueSuccessors(const CFGBlock *Block) {
     for (auto B : Block->succs())
       enqueueBlock(B);
   }
 };
 
+/// A worklist implementation for forward dataflow analysis based on a weak
+/// topological ordering of the nodes. The worklist cannot contain the same
+/// block multiple times at once.
+struct WTODataflowWorklist : DataflowWorklistBase<WTOCompare, 20> {
+  WTODataflowWorklist(const CFG &Cfg, const WTOCompare &Cmp)
+      : DataflowWorklistBase(Cfg, Cmp) {}
+
+  void enqueueSuccessors(const CFGBlock *Block) {
+    for (auto B : Block->succs())
+      enqueueBlock(B);
+  }
+};
+
 /// A worklist implementation for backward dataflow 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()) {}
+            Cfg, Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {}
 
   void enqueuePredecessors(const CFGBlock *Block) {
     for (auto B : Block->preds())
       enqueueBlock(B);
   }
 };
 
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H

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 "clang/Analysis/CFG.h"
 #include "CFGBuildResult.h"
 #include "clang/AST/Decl.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Analysis/Analyses/IntervalPartition.h"
 #include "clang/Analysis/AnalysisDeclContext.h"
-#include "clang/Analysis/CFG.h"
 #include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
 #include "clang/Tooling/Tooling.h"
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <algorithm>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace analysis {
 namespace {
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"
+                     "  while (a < 6)\n"
+                     "    ++a;\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);
for (const auto *B : *AC.getAnalysis<PostOrderCFGView>())
     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()));
   }
 
+  // RPO: 876321054
+  // WTO: 876534210
+  // So, we construct the WTO order accordingly from the reference order.
+  std::vector<const CFGBlock *> WTOOrder = {
+      ReferenceOrder[0], ReferenceOrder[1], ReferenceOrder[2],
+      ReferenceOrder[7], ReferenceOrder[3], ReferenceOrder[8],
+      ReferenceOrder[4], ReferenceOrder[5], ReferenceOrder[6]};
+
+  {
+    using ::testing::ElementsAreArray;
+    std::optional<WeakTopologicalOrdering> WTO = getIntervalWTO(*CFG);
+    ASSERT_TRUE(WTO);
+    WTOCompare WCmp(*WTO);
+    WTODataflowWorklist WTOWorklist(*CFG, WCmp);
+    for (const auto *B : *CFG)
+      WTOWorklist.enqueueBlock(B);
+
+    std::vector<const CFGBlock *> WTONodes;
+    while (const CFGBlock *B = WTOWorklist.dequeue())
+      WTONodes.push_back(B);
+
+    EXPECT_THAT(WTONodes, ElementsAreArray(WTOOrder));
+  }
+
   std::reverse(ReferenceOrder.begin(), ReferenceOrder.end());
 
   {
     BackwardDataflowWorklist BackwardWorklist(*CFG, AC);
     for (const auto *B : *CFG)
       BackwardWorklist.enqueueBlock(B);
 
     std::vector<const CFGBlock *> BackwardNodes;