From 23ce9383ca07260120df55200110373c11a5d2ff Mon Sep 17 00:00:00 2001
From: Florian Hahn <flo@fhahn.com>
Date: Wed, 4 Jan 2023 13:59:22 +0000
Subject: [PATCH] [ConstraintElim] Add option to limit number of rows tracked
 in system.

Once the constraint system grows too large in terms of number of rows,
queries can become very slow. This patch adds a new option to limit the
number of rows tracked.

The python script below can be used to generate worst-case IR with a
chain of conditional branches with N branches.

With this limit, we get the following runtimes:
* python3 generate.py 100:   0.1s
* python3 generate.py 1000:  2s
* python3 generate.py 10000: 4s

Without the limit, the case with 1000 chained conditions takes 20+
seconds.

generate.py:
    import sys

    N = int(sys.argv[1])

    args = []
    checks = []

    for i in range(0, N):
        args.append('i32 %l{}'.format(i))
        checks.append("""
    bb{0}:
      %c{0} = icmp uge i32 %l{0}, 100
      br i1 %c{0}, label %bb{1}, label %exit
    """.format(i, i+1))

    print("""
    define i1 @foo({0}) {{
    {1}

    bb{2}:
      %c{2} = icmp uge i32 %l0, 100
      ret i1 %c{2}

    exit:
      ret i1 false
    }}
    """.format(' ,'.join(args), '\n'.join(checks), N))

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D140926
---
 .../Transforms/Scalar/ConstraintElimination.cpp    | 12 +++++
 .../ConstraintElimination/max-row-limit.ll         | 57 ++++++++++++++++++++++
 2 files changed, 69 insertions(+)
 create mode 100644 llvm/test/Transforms/ConstraintElimination/max-row-limit.ll

diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
index 354796d..12fcb6a 100644
--- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
@@ -27,6 +27,7 @@
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/DebugCounter.h"
 #include "llvm/Support/MathExtras.h"
@@ -43,6 +44,10 @@ STATISTIC(NumCondsRemoved, "Number of instructions removed");
 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",
               "Controls which conditions are eliminated");
 
+static cl::opt<unsigned>
+    MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden,
+            cl::desc("Maximum number of rows to keep in constraint system"));
+
 static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max();
 static int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min();
 
@@ -1017,6 +1022,13 @@ static bool eliminateConstraints(Function &F, DominatorTree &DT) {
     Value *Cmp = CB.Inst;
     match(Cmp, m_Intrinsic<Intrinsic::assume>(m_Value(Cmp)));
     if (match(Cmp, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
+      if (Info.getCS(CmpInst::isSigned(Pred)).size() > MaxRows) {
+        LLVM_DEBUG(
+            dbgs()
+            << "Skip adding constraint because system has too many rows.\n");
+        continue;
+      }
+
       // Use the inverse predicate if required.
       if (CB.Not)
         Pred = CmpInst::getInversePredicate(Pred);
diff --git a/llvm/test/Transforms/ConstraintElimination/max-row-limit.ll b/llvm/test/Transforms/ConstraintElimination/max-row-limit.ll
new file mode 100644
index 0000000..2f830b7
--- /dev/null
+++ b/llvm/test/Transforms/ConstraintElimination/max-row-limit.ll
@@ -0,0 +1,57 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=constraint-elimination -S %s | FileCheck --check-prefixes=COMMON,SIMP %s
+; RUN: opt -passes=constraint-elimination -constraint-elimination-max-rows=4 -S %s | FileCheck --check-prefixes=COMMON,SIMP %s
+; RUN: opt -passes=constraint-elimination -constraint-elimination-max-rows=3 -S %s | FileCheck --check-prefixes=COMMON,NOSIMP %s
+
+
+define i1 @test_max_row_limit(i32 %l0, i32 %l1, i32 %l2, i32 %l3, i32 %l4) {
+; COMMON-LABEL: @test_max_row_limit(
+; COMMON-NEXT:  bb0:
+; COMMON-NEXT:    [[C0:%.*]] = icmp uge i32 [[L0:%.*]], 100
+; COMMON-NEXT:    br i1 [[C0]], label [[BB1:%.*]], label [[EXIT:%.*]]
+; COMMON:       bb1:
+; COMMON-NEXT:    [[C1:%.*]] = icmp uge i32 [[L1:%.*]], 100
+; COMMON-NEXT:    br i1 [[C1]], label [[BB2:%.*]], label [[EXIT]]
+; COMMON:       bb2:
+; COMMON-NEXT:    [[C2:%.*]] = icmp uge i32 [[L2:%.*]], 100
+; COMMON-NEXT:    br i1 [[C2]], label [[BB3:%.*]], label [[EXIT]]
+; COMMON:       bb3:
+; COMMON-NEXT:    [[C3:%.*]] = icmp uge i32 [[L3:%.*]], 100
+; COMMON-NEXT:    br i1 [[C3]], label [[BB4:%.*]], label [[EXIT]]
+; COMMON:       bb4:
+; COMMON-NEXT:    [[C4:%.*]] = icmp uge i32 [[L4:%.*]], 100
+; COMMON-NEXT:    br i1 [[C4]], label [[BB5:%.*]], label [[EXIT]]
+; COMMON:       bb5:
+; COMMON-NEXT:    [[C5:%.*]] = icmp uge i32 [[L4]], 100
+; SIMP-NEXT:      ret i1 true
+; NOSIMP-NEXT:    ret i1 [[C5]]
+; COMMON:       exit:
+; COMMON-NEXT:    ret i1 false
+;
+bb0:
+  %c0 = icmp uge i32 %l0, 100
+  br i1 %c0, label %bb1, label %exit
+
+bb1:
+  %c1 = icmp uge i32 %l1, 100
+  br i1 %c1, label %bb2, label %exit
+
+bb2:
+  %c2 = icmp uge i32 %l2, 100
+  br i1 %c2, label %bb3, label %exit
+
+bb3:
+  %c3 = icmp uge i32 %l3, 100
+  br i1 %c3, label %bb4, label %exit
+
+bb4:
+  %c4 = icmp uge i32 %l4, 100
+  br i1 %c4, label %bb5, label %exit
+
+bb5:
+  %c5 = icmp uge i32 %l4, 100
+  ret i1 %c5
+
+exit:
+  ret i1 false
+}
-- 
2.7.4