[clang][dataflow] Optimize case of degenerate `do-while` loops.

[ymandel]

Summary

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.

[ymandel]

This approach is buggy. Pulling back until I have a proper fix.

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 #include <memory>
 #include <optional>
 #include <system_error>
 #include <utility>
 #include <vector>
 
 #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"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
 #include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
 #include "clang/Analysis/FlowSensitive/Transfer.h"
 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #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"
 
 namespace clang {
 namespace dataflow {
 
 /// Returns the index of `Block` in the successors of `Pred`.
 static int blockIndexInPredecessor(const CFGBlock &Pred,
                                    const CFGBlock &Block) {
   auto BlockPos = llvm::find_if(
       Pred.succs(), [&Block](const CFGBlock::AdjacentBlock &Succ) {
         return Succ && Succ->getBlockID() == Block.getBlockID();
       });
   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()) {
       case Stmt::WhileStmtClass:
       case Stmt::DoStmtClass:
       case Stmt::ForStmtClass:
         return true;
       default:
while (const CFGBlock *Block = Worklist.dequeue()) {
     }
 
     BlockStates[Block->getBlockID()] = std::move(NewBlockState);
 
     // Do not add unreachable successor blocks to `Worklist`.
     if (Block->hasNoReturnElement())
       continue;
 
+    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.
 
   if (PostVisitCFG) {
     for (const CFGBlock *Block : CFCtx.getCFG()) {
       // Skip blocks that were not evaluated.
       if (!BlockStates[Block->getBlockID()])