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

[Yitzhak Mandelbaum via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rG9824ec875cec: [clang][dataflow] Refactor `DataflowWorklist` 
types and add a WTO version. (authored by ymandel).

Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D153071

Files:
  clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h
  clang/unittests/Analysis/CFGTest.cpp


Index: clang/unittests/Analysis/CFGTest.cpp
===================================================================
--- clang/unittests/Analysis/CFGTest.cpp
+++ clang/unittests/Analysis/CFGTest.cpp
@@ -6,13 +6,15 @@
 //
 //===----------------------------------------------------------------------===//
 
+#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>
@@ -244,6 +246,8 @@
 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"
@@ -272,6 +276,30 @@
                            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());
 
   {
Index: clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h
+++ clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h
@@ -12,6 +12,7 @@
 #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"
@@ -21,16 +22,13 @@
 /// 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()]) {
@@ -62,7 +60,7 @@
 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)
@@ -74,6 +72,19 @@
   }
 };
 
+/// 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.
@@ -81,8 +92,7 @@
     : 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())

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