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<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.
//====------------------------------------------------------------------------//
@@ -924,7 +863,12 @@
}
// Proceed with the workist.
- DataflowWorklist worklist(cfg, *ac.getAnalysis<PostOrderCFGView>());
+ ForwardDataflowWorklist worklist(cfg, ac);
+ // Populate the initial queue, treat start as analyzed.
+ for (const auto *B : *ac.getAnalysis<PostOrderCFGView>()) {
+ if (B != &cfg.getEntry())
+ worklist.enqueueBlock(B);
+ }
llvm::BitVector previouslyVisited(cfg.getNumBlockIDs());
worklist.enqueueSuccessors(&cfg.getEntry());
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 <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:
@@ -136,7 +89,7 @@
}
return A;
}
-}
+} // namespace
void LiveVariables::Observer::anchor() { }
@@ -218,7 +171,7 @@
void VisitUnaryOperator(UnaryOperator *UO);
void Visit(Stmt *S);
};
-}
+} // namespace
static const VariableArrayType *FindVA(QualType Ty) {
const Type *ty = Ty.getTypePtr();
@@ -555,7 +508,7 @@
// 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.
Index: clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h
===================================================================
--- /dev/null
+++ clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h
@@ -0,0 +1,86 @@
+//===- 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 {
+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);
+ }
+};
+
+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);
+ }
+};
+
+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
\ No newline at end of file
Index: clang/include/clang/Analysis/FlowSensitive/DataflowValues.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowValues.h
+++ clang/include/clang/Analysis/FlowSensitive/DataflowValues.h
@@ -168,4 +168,4 @@
};
} // end namespace clang
-#endif
+#endif // LLVM_CLANG_ANALYSES_DATAFLOW_VALUES
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
