[clang][dataflow] Change iteration algorithm to use WTO instead of reverse post order.

[ymandel]

Summary

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.

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 
 llvm::Expected<std::vector<std::optional<TypeErasedDataflowAnalysisState>>>
 runTypeErasedDataflowAnalysis(
     const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis,
     const Environment &InitEnv,
     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);
 
   // The entry basic block doesn't contain statements so it can be skipped.
   const CFGBlock &Entry = CFCtx.getCFG().getEntry();
   BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
                                      InitEnv};

clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp

 recordState(Elements=0, Branches=0, Joins=0)
 enterElement(b)
 transfer()
 recordState(Elements=1, Branches=0, Joins=0)
 enterElement(b (ImplicitCastExpr, LValueToRValue, _Bool))
 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)
 
 enterBlock(1)
 recordState(Elements=6, Branches=2, Joins=1)
 enterElement(b ? p : q)
 transfer()
 recordState(Elements=7, Branches=2, Joins=1)

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(
       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
          ASTContext &ASTCtx) {
         // The node after the while-true is pruned because it is trivially
         // known to be unreachable.
         ASSERT_TRUE(Results.empty());
       });
 }
 
+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 {
       int Foo;
     };
 
     struct B {
       int Bar;