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

[Yitzhak Mandelbaum via Phabricator via cfe-commits]

ymandel updated this revision to Diff 431761.
ymandel added a comment.

Reinstated absolute limit of 2^16.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D126316/new/

https://reviews.llvm.org/D126316

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
@@ -11,6 +11,7 @@
 //
 
//===----------------------------------------------------------------------===//
 
+#include <algorithm>
 #include <memory>
 #include <system_error>
 #include <utility>
@@ -330,10 +331,17 @@
   // 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,



Index: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -11,6 +11,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include <algorithm>
 #include <memory>
 #include <system_error>
 #include <utility>
@@ -330,10 +331,17 @@
   // 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,

_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits