xazax.hun updated this revision to Diff 236873.
xazax.hun added a comment.
- Prepopulating the worklist for UninitializedValues seems to be redundant.
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D72380/new/
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,7 @@
}
// 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);
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
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
