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

[Yitzhak Mandelbaum via Phabricator via cfe-commits]

ymandel created this revision.
ymandel added reviewers: xazax.hun, li.zhe.hua, sgatev.
Herald added subscribers: tschuett, steakhal, rnkovacs.
Herald added a project: All.
ymandel requested review of this revision.
Herald added a project: clang.

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.


Repository:
  rG LLVM Github Monorepo

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
@@ -332,8 +332,9 @@
   // FIXME: Consider making the maximum number of iterations configurable.
   // 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;
+  const uint32_t MaxIterations = MaxAverageVisitsPerBlock * BlockStates.size();
   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
@@ -332,8 +332,9 @@
   // FIXME: Consider making the maximum number of iterations configurable.
   // 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;
+  const uint32_t MaxIterations = MaxAverageVisitsPerBlock * BlockStates.size();
   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

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

[Dmitri Gribenko via Phabricator via cfe-commits]

gribozavr2 added inline comments.



Comment at: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp:336
+  static constexpr uint32_t MaxAverageVisitsPerBlock = 4;
+  const uint32_t MaxIterations = MaxAverageVisitsPerBlock * BlockStates.size();
   uint32_t Iterations = 0;

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


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D126316

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

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

[Thorsten via Phabricator via cfe-commits]

tschuett added a comment.

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


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D126316

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

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

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun added a comment.

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.


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D126316

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

[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 
 #include 
 #include 
 #include 
@@ -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 
 #include 
 #include 
 #include 
@@ -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

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

[Yitzhak Mandelbaum via Phabricator via cfe-commits]

ymandel added a comment.

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...


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D126316

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

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

[Yitzhak Mandelbaum via Phabricator via cfe-commits]

This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.
Closed by commit rG6eb9e0f5ebb9: [clang][dataflow] Make limit on 
fixpoint-algorithm iterations proportional to… (authored by ymandel).

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 
 #include 
 #include 
 #include 
@@ -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 
 #include 
 #include 
 #include 
@@ -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