[clang][dataflow] Make limit on fixpoint-algorithm iterations proportional to size of CFG.

[ymandel]

Summary

Currently, the maximum number of iterations of the loop for finding the fixpoint
of the dataflow analysis is set at 2^16. When things go wrong in an analysis,
this can be far too large. This patch changes the limit to be proportional to
the size of the CFG, which will generally be far smaller than 2^16 (while still
maintaining 2^16 as the absolute limit).

[gribozavr2]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

339

Could you cap the computed number at 1<<16 still?

[tschuett]

or min(MaxAverageVisitsPerBlock * BlockStates.size(), 2^16);

[xazax.hun]

An alternative approach is to maintain separate counters for back edges and bail if those reach a certain limit. But this global limit is way simpler, so it looks good to me.

[ymandel]

Reinstated absolute limit of 2^16.

[ymandel]

In D126316#3535057, @tschuett wrote:

or min(MaxAverageVisitsPerBlock * BlockStates.size(), 2^16);

Good idea, thx.

In D126316#3535077, @xazax.hun wrote:

An alternative approach is to maintain separate counters for back edges and bail if those reach a certain limit. But this global limit is way simpler, so it looks good to me.

Agreed -- this seems a better approach. Added as a FIXME. We should revisit...

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 //===- TypeErasedDataflowAnalysis.cpp -------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines type-erased base types and functions for building dataflow
 //  analyses that run over Control-Flow Graphs (CFGs).
 //
 //===----------------------------------------------------------------------===//
 
+#include <algorithm>
 #include <memory>
 #include <system_error>
 #include <utility>
 #include <vector>
 
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/OperationKinds.h"
 #include "clang/AST/StmtVisitor.h"
runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx,
   BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
                                      InitEnv};
   Worklist.enqueueSuccessors(&Entry);
 
   // Bugs in lattices and transfer functions can prevent the analysis from
   // converging. To limit the damage (infinite loops) that these bugs can cause,
   // limit the number of iterations.
   // FIXME: Consider making the maximum number of iterations configurable.
+  // FIXME: Consider restricting the number of backedges followed, rather than
+  // iterations.
   // FIXME: Set up statistics (see llvm/ADT/Statistic.h) to count average number
   // of iterations, number of functions that time out, etc.
+  static constexpr uint32_t MaxAverageVisitsPerBlock = 4;
+  static constexpr uint32_t AbsoluteMaxIterations = 1 << 16;
+  const uint32_t RelativeMaxIterations =
+      MaxAverageVisitsPerBlock * BlockStates.size();
+  const uint32_t MaxIterations =
+      std::min(RelativeMaxIterations, AbsoluteMaxIterations);
   uint32_t Iterations = 0;
-  static constexpr uint32_t MaxIterations = 1 << 16;
   while (const CFGBlock *Block = Worklist.dequeue()) {
     if (++Iterations > MaxIterations) {
       return llvm::createStringError(std::errc::timed_out,
                                      "maximum number of iterations reached");
     }
 
     const llvm::Optional<TypeErasedDataflowAnalysisState> &OldBlockState =
         BlockStates[Block->getBlockID()];