ymandel created this revision.
ymandel added reviewers: xazax.hun, gribozavr.
Herald added a subscriber: martong.
Herald added a reviewer: NoQ.
Herald added a project: All.
ymandel requested review of this revision.
Herald added a project: clang.
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.
Repository:
rG LLVM Github Monorepo
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
