From 4ceecc820b7197c2f302aa235875eb6619a397c3 Mon Sep 17 00:00:00 2001
From: Florian Hahn <flo@fhahn.com>
Date: Sat, 5 Dec 2020 10:52:50 +0000
Subject: [PATCH] [ConstraintElimination] Handle constraints with all zero var
 coeffs.

Constraints where all variable coefficients are 0 do not add any useful
information. When checking, we can check if they are always true/false.
---
 llvm/include/llvm/Analysis/ConstraintSystem.h      | 13 ++++--
 llvm/lib/Analysis/ConstraintSystem.cpp             |  5 +++
 .../Transforms/Scalar/ConstraintElimination.cpp    |  6 ++-
 .../ConstraintElimination/empty-constraint.ll      | 47 ++++++++++++++++++++++
 4 files changed, 66 insertions(+), 5 deletions(-)
 create mode 100644 llvm/test/Transforms/ConstraintElimination/empty-constraint.ll

diff --git a/llvm/include/llvm/Analysis/ConstraintSystem.h b/llvm/include/llvm/Analysis/ConstraintSystem.h
index f4e6dfb..2e55d5d 100644
--- a/llvm/include/llvm/Analysis/ConstraintSystem.h
+++ b/llvm/include/llvm/Analysis/ConstraintSystem.h
@@ -11,6 +11,7 @@
 
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 
 #include <string>
@@ -39,22 +40,28 @@ class ConstraintSystem {
   bool mayHaveSolutionImpl();
 
 public:
-  void addVariableRow(const SmallVector<int64_t, 8> &R) {
+  bool addVariableRow(const SmallVector<int64_t, 8> &R) {
     assert(Constraints.empty() || R.size() == Constraints.back().size());
+    // If all variable coefficients are 0, the constraint does not provide any
+    // usable information.
+    if (all_of(makeArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
+      return false;
+
     for (const auto &C : R) {
       auto A = std::abs(C);
       GCD = APIntOps::GreatestCommonDivisor({32, (uint32_t)A}, {32, GCD})
                 .getZExtValue();
     }
     Constraints.push_back(R);
+    return true;
   }
 
-  void addVariableRowFill(const SmallVector<int64_t, 8> &R) {
+  bool addVariableRowFill(const SmallVector<int64_t, 8> &R) {
     for (auto &CR : Constraints) {
       while (CR.size() != R.size())
         CR.push_back(0);
     }
-    addVariableRow(R);
+    return addVariableRow(R);
   }
 
   /// Returns true if there may be a solution for the constraints in the system.
diff --git a/llvm/lib/Analysis/ConstraintSystem.cpp b/llvm/lib/Analysis/ConstraintSystem.cpp
index d5b15e7..3df1184 100644
--- a/llvm/lib/Analysis/ConstraintSystem.cpp
+++ b/llvm/lib/Analysis/ConstraintSystem.cpp
@@ -140,6 +140,11 @@ bool ConstraintSystem::mayHaveSolution() {
 }
 
 bool ConstraintSystem::isConditionImplied(SmallVector<int64_t, 8> R) {
+  // If all variable coefficients are 0, we have 'C >= 0'. If the constant is >=
+  // 0, R is always true, regardless of the system.
+  if (all_of(makeArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
+    return R[0] >= 0;
+
   // If there is no solution with the negation of R added to the system, the
   // condition must hold based on the existing constraints.
   R = ConstraintSystem::negate(R);
diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
index b2465d2..616518c 100644
--- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
@@ -346,8 +346,10 @@ static bool eliminateConstraints(Function &F, DominatorTree &DT) {
     if (CB.Not)
       R = ConstraintSystem::negate(R);
 
-    CS.addVariableRowFill(R);
-    DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not);
+    // If R has been added to the system, queue it for removal once it goes
+    // out-of-scope.
+    if (CS.addVariableRowFill(R))
+      DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not);
   }
 
   return Changed;
diff --git a/llvm/test/Transforms/ConstraintElimination/empty-constraint.ll b/llvm/test/Transforms/ConstraintElimination/empty-constraint.ll
new file mode 100644
index 0000000..cc30da0
--- /dev/null
+++ b/llvm/test/Transforms/ConstraintElimination/empty-constraint.ll
@@ -0,0 +1,47 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -constraint-elimination -S %s | FileCheck %s
+
+; Make sure constraints where all variable coefficients are 0 are handled
+; properly.
+
+define i1 @test_1_always_false(i32 %A, i32 %B) {
+; CHECK-LABEL: @test_1_always_false(
+; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i32 [[A:%.*]], [[A]]
+; CHECK-NEXT:    br i1 [[C_1]], label [[IF_END_I16:%.*]], label [[IF_THEN_I10:%.*]]
+; CHECK:       if.then.i10:
+; CHECK-NEXT:    ret i1 false
+; CHECK:       if.end.i16:
+; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt i32 [[A]], [[A]]
+; CHECK-NEXT:    ret i1 false
+;
+  %c.1 = icmp ugt i32 %A, %A
+  br i1 %c.1, label %if.end.i16, label %if.then.i10
+
+if.then.i10:
+  ret i1 false
+
+if.end.i16:
+  %c.2 = icmp ugt i32 %A, %A
+  ret i1 %c.2
+}
+
+define i1 @test_2_always_true(i32 %A, i32 %B) {
+; CHECK-LABEL: @test_2_always_true(
+; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    br i1 [[C_1]], label [[IF_END_I16:%.*]], label [[IF_THEN_I10:%.*]]
+; CHECK:       if.then.i10:
+; CHECK-NEXT:    ret i1 false
+; CHECK:       if.end.i16:
+; CHECK-NEXT:    [[C_2:%.*]] = icmp uge i32 [[A]], [[A]]
+; CHECK-NEXT:    ret i1 true
+;
+  %c.1 = icmp uge i32 %A, %B
+  br i1 %c.1, label %if.end.i16, label %if.then.i10
+
+if.then.i10:
+  ret i1 false
+
+if.end.i16:
+  %c.2 = icmp uge i32 %A, %A
+  ret i1 %c.2
+}
-- 
2.7.4