ymandel created this revision.
ymandel added reviewers: xazax.hun, gribozavr2, sgatev.
Herald added subscribers: martong, rnkovacs.
Herald added a reviewer: NoQ.
Herald added a project: All.
ymandel requested review of this revision.
Herald added a project: clang.
In general, the iteration algorithm would be closer to optimal if it stabilized
loop bodies before visiting their successors. There is a special case of this
situation which is particularly problematic in practice: degenerate loops of the
form `do { ... } while(0)`, which are used in some macro definitions, for
syntactic reasons. When a series of these loops appear in sequence, as in uses
of logging or tracing macro, the resulting iteration can become exponential in
running time.
This patch is a short term fix for the particular degenerate case. Long-term, we
intend to implement an iteration order (like Bourdoncle's WTO) which takes loop
stabilization into account.
Issue #60273.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D149585
Files:
clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
Index: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -20,6 +20,7 @@
#include "clang/AST/DeclCXX.h"
#include "clang/AST/OperationKinds.h"
+#include "clang/AST/Stmt.h"
#include "clang/AST/StmtVisitor.h"
#include "clang/Analysis/Analyses/PostOrderCFGView.h"
#include "clang/Analysis/CFG.h"
@@ -34,6 +35,7 @@
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Error.h"
+#include "llvm/Support/raw_ostream.h"
#define DEBUG_TYPE "clang-dataflow"
@@ -50,6 +52,15 @@
return BlockPos - Pred.succ_begin();
}
+// Detects a degenerate `do-while` loop of the form `do { ... } while(0)`. This
+// form is sometimes used in macro definitions.
+static bool isDegenerateDoWhile(const CFGBlock &B) {
+ if (const auto *D = dyn_cast_or_null<DoStmt>(B.getTerminatorStmt()))
+ if (const auto *Cond = dyn_cast<IntegerLiteral>(D->getCond()))
+ return Cond->getValue().isZero();
+ return false;
+}
+
static bool isLoopHead(const CFGBlock &B) {
if (const auto *T = B.getTerminatorStmt())
switch (T->getStmtClass()) {
@@ -468,7 +479,15 @@
if (Block->hasNoReturnElement())
continue;
- Worklist.enqueueSuccessors(Block);
+ if (isDegenerateDoWhile(*Block) && Block->succ_size() == 2)
+ // Visit the loop body only. Avoid visiting the successor of the loop to
+ // ensure that the body is visited first. Otherwise, the successor will
+ // likely be revisited after the loop body. When a series of these loops
+ // appear in sequence (such as with the use of certain macros), the
wasted
+ // work can result in exponential running times.
+ Worklist.enqueueBlock(*Block->succ_begin());
+ else
+ Worklist.enqueueSuccessors(Block);
}
// FIXME: Consider evaluating unreachable basic blocks (those that have a
// state set to `std::nullopt` at this point) to also analyze dead code.
Index: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -20,6 +20,7 @@
#include "clang/AST/DeclCXX.h"
#include "clang/AST/OperationKinds.h"
+#include "clang/AST/Stmt.h"
#include "clang/AST/StmtVisitor.h"
#include "clang/Analysis/Analyses/PostOrderCFGView.h"
#include "clang/Analysis/CFG.h"
@@ -34,6 +35,7 @@
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Error.h"
+#include "llvm/Support/raw_ostream.h"
#define DEBUG_TYPE "clang-dataflow"
@@ -50,6 +52,15 @@
return BlockPos - Pred.succ_begin();
}
+// Detects a degenerate `do-while` loop of the form `do { ... } while(0)`. This
+// form is sometimes used in macro definitions.
+static bool isDegenerateDoWhile(const CFGBlock &B) {
+ if (const auto *D = dyn_cast_or_null<DoStmt>(B.getTerminatorStmt()))
+ if (const auto *Cond = dyn_cast<IntegerLiteral>(D->getCond()))
+ return Cond->getValue().isZero();
+ return false;
+}
+
static bool isLoopHead(const CFGBlock &B) {
if (const auto *T = B.getTerminatorStmt())
switch (T->getStmtClass()) {
@@ -468,7 +479,15 @@
if (Block->hasNoReturnElement())
continue;
- Worklist.enqueueSuccessors(Block);
+ if (isDegenerateDoWhile(*Block) && Block->succ_size() == 2)
+ // Visit the loop body only. Avoid visiting the successor of the loop to
+ // ensure that the body is visited first. Otherwise, the successor will
+ // likely be revisited after the loop body. When a series of these loops
+ // appear in sequence (such as with the use of certain macros), the wasted
+ // work can result in exponential running times.
+ Worklist.enqueueBlock(*Block->succ_begin());
+ else
+ Worklist.enqueueSuccessors(Block);
}
// FIXME: Consider evaluating unreachable basic blocks (those that have a
// state set to `std::nullopt` at this point) to also analyze dead code.
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
