[MLIR][Presburger] optimize bound computation by pruning orthogonal constraints #164199

cxy-1993 · 2025-10-20T03:27:49Z

IntegerRelation uses Fourier-Motzkin elimination and Gaussian elimination to simplify constraints. These methods may repeatedly perform calculations and elimination on irrelevant variables. Preemptively eliminating irrelevant variables and their associated constraints can speed up up the calculation process.

llvmbot · 2025-10-20T03:28:17Z

@llvm/pr-subscribers-mlir-presburger

@llvm/pr-subscribers-mlir

Author: donald chen (cxy-1993)

Changes

IntegerRelation uses Fourier-Motzkin elimination and Gaussian elimination to simplify constraints. These methods may repeatedly perform calculations and elimination on irrelevant variables. Preemptively eliminating irrelevant variables and their associated constraints can speed up up the calculation process.

Full diff: https://github.com/llvm/llvm-project/pull/164199.diff

2 Files Affected:

(modified) mlir/include/mlir/Analysis/Presburger/IntegerRelation.h (+3)
(modified) mlir/lib/Analysis/Presburger/IntegerRelation.cpp (+55)

diff --git a/mlir/include/mlir/Analysis/Presburger/IntegerRelation.h b/mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
index f86535740fec9..026d84529edfb 100644
--- a/mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
+++ b/mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
@@ -511,6 +511,9 @@ class IntegerRelation {
   void projectOut(unsigned pos, unsigned num);
   inline void projectOut(unsigned pos) { return projectOut(pos, 1); }
 
+  /// Prune constraints that are irrelevant to the target variable.
+  void pruneConstraints(unsigned pos);
+
   /// Tries to fold the specified variable to a constant using a trivial
   /// equality detection; if successful, the constant is substituted for the
   /// variable everywhere in the constraint system and then removed from the
diff --git a/mlir/lib/Analysis/Presburger/IntegerRelation.cpp b/mlir/lib/Analysis/Presburger/IntegerRelation.cpp
index 0dcdd5bb97bc8..b05e872323aff 100644
--- a/mlir/lib/Analysis/Presburger/IntegerRelation.cpp
+++ b/mlir/lib/Analysis/Presburger/IntegerRelation.cpp
@@ -21,6 +21,7 @@
 #include "mlir/Analysis/Presburger/Simplex.h"
 #include "mlir/Analysis/Presburger/Utils.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Sequence.h"
 #include "llvm/ADT/SmallBitVector.h"
@@ -1723,12 +1724,66 @@ std::optional<DynamicAPInt> IntegerRelation::getConstantBoundOnDimSize(
   return minDiff;
 }
 
+void IntegerRelation::pruneConstraints(unsigned pos) {
+  llvm::DenseSet<unsigned> relatedCols({pos}), relatedRows;
+
+  llvm::SmallVector<unsigned> rowStack, colStack({pos});
+  unsigned numConstraints = getNumConstraints();
+  if (numConstraints == 0) return;
+  while (!rowStack.empty() || !colStack.empty()) {
+    if (!rowStack.empty()) {
+      unsigned currentRow = rowStack.pop_back_val();
+      for (uint64_t colIndex = 0; colIndex < getNumVars(); ++colIndex) {
+        if (currentRow < getNumInequalities()) {
+          if (atIneq(currentRow, colIndex) != 0 &&
+              relatedCols.insert(colIndex).second) {
+            colStack.push_back(colIndex);
+          }
+        } else {
+          if (atEq(currentRow - getNumInequalities(), colIndex) != 0 &&
+              relatedCols.insert(colIndex).second) {
+            colStack.push_back(colIndex);
+          }
+        }
+      }
+    } else {
+      unsigned currentCol = colStack.pop_back_val();
+      for (uint64_t rowIndex = 0; rowIndex < numConstraints; ++rowIndex) {
+        if (rowIndex < getNumInequalities()) {
+          if (atIneq(rowIndex, currentCol) != 0 &&
+              relatedRows.insert(rowIndex).second) {
+            rowStack.push_back(rowIndex);
+          }
+        } else {
+          if (atEq(rowIndex - getNumInequalities(), currentCol) != 0 &&
+              relatedRows.insert(rowIndex).second) {
+            rowStack.push_back(rowIndex);
+          }
+        }
+      }
+    }
+  }
+
+  for (int64_t constraintId = numConstraints - 1; constraintId >= 0;
+       --constraintId) {
+    if (!relatedRows.contains(constraintId)) {
+      if (constraintId >= getNumInequalities()) {
+        removeEquality(constraintId - getNumInequalities());
+      } else {
+        removeInequality(constraintId);
+      }
+    }
+  }
+}
+
 template <bool isLower>
 std::optional<DynamicAPInt>
 IntegerRelation::computeConstantLowerOrUpperBound(unsigned pos) {
   assert(pos < getNumVars() && "invalid position");
   // Project to 'pos'.
+  pruneConstraints(pos);
   projectOut(0, pos);
+  pruneConstraints(0);
   projectOut(1, getNumVars() - 1);
   // Check if there's an equality equating the '0'^th variable to a constant.
   int eqRowIdx = findEqualityToConstant(/*pos=*/0, /*symbolic=*/false);

github-actions · 2025-10-20T03:29:39Z

✅ With the latest revision this PR passed the C/C++ code formatter.

cxy-1993 · 2025-10-22T13:51:03Z

ping

Groverkss · 2025-10-24T06:40:16Z

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

+void IntegerRelation::pruneConstraints(unsigned pos) {
+  llvm::DenseSet<unsigned> relatedCols({pos}), relatedRows;
+
+  llvm::SmallVector<unsigned> rowStack, colStack({pos});


@Superty This seems like something we already have implemented somewhere? Can you review this PR?

Off the top of my head I don't remember such a thing

Superty · 2025-10-25T16:27:13Z

Hi @cxy-1993, sorry about the delay here. In "Prune constraints that are irrelevant to the target variable.", how is irrelevant defined?

cxy-1993 · 2025-10-27T02:05:57Z

Hi @cxy-1993, sorry about the delay here. In "Prune constraints that are irrelevant to the target variable.", how is irrelevant defined?

In my opinion, the definition of variable irrelevance is as follows: If variables are considered as nodes and equations/inequalities as edges between nodes, a set of constraints forms an undirected graph. Variables in different connected components are irrelevant. This patch is about finding all nodes within the same connected component and then removing all nodes and related edges (equations and inequalities) that are not in the same connected component.

cxy-1993 · 2025-10-30T06:13:23Z

ping @Superty

cxy-1993 · 2025-11-03T07:23:44Z

ping @Superty

Superty · 2025-11-04T00:09:46Z

I probably won't be able to look at this for a few more weeks, sorry. I would suggest adding some more documentation explaining what irrelevant means though. Is there a geometric interpretation of the definition? Maybe it makes sense to explain it with reference to Fourier motzkin?

The implementation could also use some more documentation. Thanks!

…ds of an Integer Relation IntegerRelation uses Fourier-Motzkin elimination and Gaussian elimination to simplify constraints. These methods may repeatedly perform calculations and elimination on irrelevant variables. Preemptively eliminating irrelevant variables and their associated constraints can speed up up the calculation process.

cxy-1993 · 2025-11-05T11:41:11Z

I probably won't be able to look at this for a few more weeks, sorry. I would suggest adding some more documentation explaining what irrelevant means though. Is there a geometric interpretation of the definition? Maybe it makes sense to explain it with reference to Fourier motzkin?

The implementation could also use some more documentation. Thanks!

I have now added detailed information regarding the function's mechanism and usage. Please let me know if you feel anything further is needed. Thank you for your time.

cxy-1993 · 2025-11-25T07:51:44Z

Could you please take some time to review this patch now? Thank you very much. @Superty

Superty

Thanks for your contribution and patience. I left a review!

(I removed the mention of "compilation time" from the title, I think we should reserve that phrase for the compilation time of the library)

Superty · 2025-11-30T19:21:57Z

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h

+  /// have no impact on the solution space of Component 1.
+  /// This function prunes irrelevant constraints by identifying all variables
+  /// and constraints that belong to the same connected component as the
+  /// target variable.


Can we change the name to pruneOrthogonalConstraints or something? I think that makes it more specific what's going on. We can also change the parameter name pos to var or something to make it clearer what it's supposed to be.

Superty · 2025-11-30T19:23:03Z

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

+void IntegerRelation::pruneConstraints(unsigned pos) {
+  llvm::DenseSet<unsigned> relatedCols({pos}), relatedRows;
+
+  // Early quit if constraints is empty.


nit: we usually call this early exit!

Superty · 2025-11-30T19:24:11Z

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

+  // variable, to identify all variables(recorded in relatedCols) and
+  // constraints(recorded in relatedRows) belonging to the same connected


nit: please leave a space before opening parentheses (

Superty · 2025-11-30T19:33:58Z

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

+        if (rowIndex < getNumInequalities()) {
+          if (atIneq(rowIndex, currentCol) != 0 &&
+              relatedRows.insert(rowIndex).second) {
+            rowStack.push_back(rowIndex);
+          }
+        } else {
+          if (atEq(rowIndex - getNumInequalities(), currentCol) != 0 &&
+              relatedRows.insert(rowIndex).second) {
+            rowStack.push_back(rowIndex);
+          }
+        }


There seems to be a lot of duplication here and above. We should pull out a function (maybe just a lambda) called atConstraint or something to avoid the duplicated if/else.

Superty · 2025-11-30T19:34:20Z

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

+      unsigned currentCol = colStack.pop_back_val();
+      // Push all constrains that accociated to this variable to relatedRows
+      // and rowStack.
+      for (uint64_t rowIndex = 0; rowIndex < numConstraints; ++rowIndex) {


You can just use an unsigned for the rowIndex.

Superty · 2025-11-30T19:34:56Z

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

+      // Push all constrains that accociated to this variable to relatedRows
+      // and rowStack.


Please fix the spelling/grammar on this line (and above).

Superty · 2025-11-30T19:37:29Z

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

  // Project to 'pos'.
+  pruneConstraints(pos);
  projectOut(0, pos);
+  pruneConstraints(0);


Can you write a comment here explaining why the second pruneConstraints might be helpful?

Superty · 2025-11-30T19:37:49Z

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

+  }
+
+  // Prune all constraints not related to target variable.
+  for (int64_t constraintId = numConstraints - 1; constraintId >= 0;


You can just use an int for the constraintId.

Superty · 2025-11-30T19:40:19Z

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

+    if (!relatedRows.contains(constraintId)) {
+      if (constraintId >= getNumInequalities()) {


It's preferred to early-exit if constraintId is relevant and then do the removal otherwise, to reduce nesting (https://llvm.org/docs/CodingStandards.html#use-early-exits-and-continue-to-simplify-code)

Superty · 2025-11-30T19:43:33Z

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h

+  /// The set of constraints (equations/inequalities) can be modeled as an
+  /// undirected graph where:


Can you write a 1-2 line summary at the top, so that people can quickly understand what the function does, while keeping the details below? You can write that the function removes some constraints that do not impose any bound on the specified variable.

cxy-1993 requested review from Groverkss and Superty as code owners October 20, 2025 03:27

llvmbot added mlir mlir:presburger labels Oct 20, 2025

cxy-1993 force-pushed the opt-intrelation branch from ababef2 to ee2806f Compare October 20, 2025 06:34

Groverkss reviewed Oct 24, 2025

View reviewed changes

cxy-1993 force-pushed the opt-intrelation branch from ee2806f to 5e01741 Compare November 5, 2025 11:39

Superty changed the title ~~[mlir][presburger] Optimize the compilation time for calculating bounds of an Integer Relation~~ [MLIR][Presburger] improve performance of bound computation by pruning orthogonal constraints Nov 30, 2025

Superty changed the title ~~[MLIR][Presburger] improve performance of bound computation by pruning orthogonal constraints~~ [MLIR][Presburger] improve bound computation performance by pruning orthogonal constraints Nov 30, 2025

Superty changed the title ~~[MLIR][Presburger] improve bound computation performance by pruning orthogonal constraints~~ [MLIR][Presburger] optimize bound computation by pruning orthogonal constraints Nov 30, 2025

Superty requested changes Nov 30, 2025

View reviewed changes

		// variable, to identify all variables(recorded in relatedCols) and
		// constraints(recorded in relatedRows) belonging to the same connected

		// Push all constrains that accociated to this variable to relatedRows
		// and rowStack.

		if (!relatedRows.contains(constraintId)) {
		if (constraintId >= getNumInequalities()) {

		/// The set of constraints (equations/inequalities) can be modeled as an
		/// undirected graph where:

[MLIR][Presburger] optimize bound computation by pruning orthogonal constraints #164199

Are you sure you want to change the base?

[MLIR][Presburger] optimize bound computation by pruning orthogonal constraints #164199

Conversation

cxy-1993 commented Oct 20, 2025

Uh oh!

llvmbot commented Oct 20, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions bot commented Oct 20, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

cxy-1993 commented Oct 22, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Superty commented Oct 25, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

cxy-1993 commented Oct 27, 2025

Uh oh!

cxy-1993 commented Oct 30, 2025

Uh oh!

cxy-1993 commented Nov 3, 2025

Uh oh!

Superty commented Nov 4, 2025

Uh oh!

cxy-1993 commented Nov 5, 2025

Uh oh!

cxy-1993 commented Nov 25, 2025

Uh oh!

Superty left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

llvmbot commented Oct 20, 2025 •

edited

Loading

github-actions bot commented Oct 20, 2025 •

edited

Loading

Superty commented Oct 25, 2025 •

edited

Loading