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.
This patch replaces use of the reverse-post order (RPO) based worklist with one
based on a weak topological order (WTO). The WTO gives better guarantees on
maximum number of times we'll visit each node in the CFG. The new test case
fails (because of too many iterations) with RPO but passes with WTO.
Ideally, we could iterate using WTO directly without a worklist, but this isn't
yet possible because our widening is limited to booleans. Once we have full
widening at loop heads, we can simplify further to guide the iteration directly
from the WTO's structure.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D153078
Files:
clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
Index: clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
===================================================================
--- clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
+++ clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
@@ -2673,6 +2673,49 @@
});
}
+TEST(TransferTest, SequencedWhilesNoTimeout) {
+ std::string Code = R"(
+ void target() {
+ bool b = true;
+ while (b) {
+ b = false;
+ }
+ b = true;
+ while (b) {
+ b = false;
+ }
+ b = true;
+ while (b) {
+ b = false;
+ }
+ b = true;
+ while (b) {
+ b = false;
+ }
+ b = true;
+ while (b) {
+ b = false;
+ }
+ b = true;
+ while (b) {
+ b = false;
+ }
+ b = true;
+ while (b) {
+ b = false;
+ }
+ (void)0;
+ /*[[p]]*/
+ }
+ )";
+ runDataflow(
+ Code,
+ [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+ ASTContext &ASTCtx) {
+ EXPECT_EQ(Results.size(), 1u);
+ });
+}
+
TEST(TransferTest, AggregateInitialization) {
std::string BracesCode = R"(
struct A {
Index: clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
===================================================================
--- clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
+++ clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
@@ -123,17 +123,17 @@
transfer()
recordState(Elements=2, Branches=0, Joins=0)
-enterBlock(3)
-transferBranch(0)
+enterBlock(2)
+transferBranch(1)
recordState(Elements=2, Branches=1, Joins=0)
-enterElement(q)
+enterElement(p)
transfer()
recordState(Elements=3, Branches=1, Joins=0)
-enterBlock(2)
-transferBranch(1)
+enterBlock(3)
+transferBranch(0)
recordState(Elements=2, Branches=1, Joins=0)
-enterElement(p)
+enterElement(q)
transfer()
recordState(Elements=3, Branches=1, Joins=0)
Index: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -395,8 +395,15 @@
std::function<void(const CFGElement &,
const TypeErasedDataflowAnalysisState &)>
PostVisitCFG) {
- PostOrderCFGView POV(&CFCtx.getCFG());
- ForwardDataflowWorklist Worklist(CFCtx.getCFG(), &POV);
+ std::optional<WeakTopologicalOrdering> WTO = getIntervalWTO(CFCtx.getCFG());
+ if (!WTO)
+ return llvm::createStringError(std::errc::invalid_argument,
+ "input CFG not reducible");
+ WTOCompare Cmp(*WTO);
+ WTODataflowWorklist Worklist(CFCtx.getCFG(), Cmp);
+ // FIXME: provide fallback?
+ // PostOrderCFGView POV(&CFCtx.getCFG());
+ // ForwardDataflowWorklist Worklist(CFCtx.getCFG(), &POV);
std::vector<std::optional<TypeErasedDataflowAnalysisState>> BlockStates(
CFCtx.getCFG().size(), std::nullopt);
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
