diff --git a/llvm/include/llvm/Analysis/ConstraintSystem.h b/llvm/include/llvm/Analysis/ConstraintSystem.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Analysis/ConstraintSystem.h @@ -0,0 +1,52 @@ +//===- ConstraintSystem.h - A system of linear constraints. --------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_CONSTRAINTSOLVER_H +#define LLVM_ANALYSIS_CONSTRAINTSOLVER_H + +#include "llvm/ADT/APInt.h" +#include "llvm/ADT/SmallVector.h" +#include + +namespace llvm { + +class ConstraintSystem { + /// Current linear constraints in the system. + /// An entry of the form c0, c1, ... cn represents the following constraint: + /// c0 >= v0 * c1 + .... + v{n-1} * cn + SmallVector, 4> Constraints; + + /// Current greatest common divisor for all coefficients in the system. + uint32_t GCD = 1; + + uint32_t NumVariables = 0; + + // Eliminate constraints from the system using Fourier–Motzkin elimination. + bool eliminateUsingFM(); + + /// Print the constraints in the system. + void dump(); + +public: + void addVariableRow(const SmallVector &R) { + assert(Constraints.empty() || R.size() == Constraints.back().size()); + for (auto &C : R) { + auto A = std::abs(C); + GCD = APIntOps::GreatestCommonDivisor({32, (uint32_t)A}, {32, GCD}) + .getZExtValue(); + } + Constraints.push_back(R); + NumVariables = (uint32_t)std::max((size_t)NumVariables, R.size()); + } + + /// Retuns true if there may be a solution for the constraints in the system. + bool mayHaveSolution(); +}; +} // namespace llvm + +#endif diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -39,6 +39,7 @@ CodeMetrics.cpp ConstantFolding.cpp DDG.cpp + ConstraintSystem.cpp Delinearization.cpp DemandedBits.cpp DependenceAnalysis.cpp diff --git a/llvm/lib/Analysis/ConstraintSystem.cpp b/llvm/lib/Analysis/ConstraintSystem.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Analysis/ConstraintSystem.cpp @@ -0,0 +1,111 @@ +//===- ConstraintSytem.cpp - A system of linear constraints. ----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/ConstraintSystem.h" +#include "llvm/Support/Debug.h" + +#include +#include +#include + +using namespace llvm; + +bool ConstraintSystem::eliminateUsingFM() { + // Implementation of Fourier–Motzkin elimination, with some tricks from the + // paper Pugh, William. "The Omega test: a fast and practical integer + // programming algorithm for dependence + // analysis." + // Supercomputing'91: Proceedings of the 1991 ACM/ + // IEEE conference on Supercomputing. IEEE, 1991. + assert(!Constraints.empty()); + NumVariables = Constraints[0].size(); + SmallVector, 4> NewSystem; + + uint32_t NewGCD = 1; + // FIXME do not use copy + for (unsigned R1 = 0; R1 < Constraints.size(); R1++) { + if (Constraints[R1][1] == 0) { + SmallVector NR; + NR.push_back(Constraints[R1][0]); + for (unsigned i = 2; i < Constraints[0].size(); i++) { + NR.push_back(Constraints[R1][i]); + } + NewSystem.push_back(std::move(NR)); + continue; + } + + // FIXME do not use copy + bool EliminatedInRow = false; + for (unsigned R2 = R1 + 1; R2 < Constraints.size(); R2++) { + if (R1 == R2) + continue; + + // FIXME: can we do better than just dropping things here? + if (Constraints[R2][1] == 0) + continue; + + if ((Constraints[R1][1] < 0 && Constraints[R2][1] < 0) || + (Constraints[R1][1] > 0 && Constraints[R2][1] > 0)) + continue; + + unsigned LowerR = R1; + unsigned UpperR = R2; + if (Constraints[UpperR][1] < 0) + std::swap(LowerR, UpperR); + + SmallVector NR; + for (unsigned i = 0; i < NumVariables; i++) { + if (i == 1) + continue; + NR.push_back(Constraints[UpperR][i] * + ((-1) * Constraints[LowerR][1] / GCD) + + Constraints[LowerR][i] * (Constraints[UpperR][1] / GCD)); + NewGCD = APIntOps::GreatestCommonDivisor({32, (uint32_t)NR.back()}, + {32, NewGCD}) + .getZExtValue(); + } + NewSystem.push_back(std::move(NR)); + EliminatedInRow = true; + } + } + Constraints = std::move(NewSystem); + GCD = NewGCD; + + return true; +} + +bool ConstraintSystem::mayHaveSolution() { + while (!Constraints.empty() && Constraints[0].size() > 1) { + eliminateUsingFM(); + } + + if (Constraints.empty()) + return true; + if (Constraints[0].size() > 1) + return true; + for (auto &R : Constraints) { + if (R[0] < 0) + return false; + } + return true; +} + +void ConstraintSystem::dump() { + if (Constraints.empty()) + return; + + std::cout << "c\t"; + for (unsigned i = 1; i < Constraints[0].size(); i++) + std::cout << "x" << i << "\t"; + std::cout << "\n"; + for (auto &R : Constraints) { + for (auto a : R) + std::cout << a << "\t"; + std::cout << "\n"; + } +} diff --git a/llvm/unittests/Analysis/CMakeLists.txt b/llvm/unittests/Analysis/CMakeLists.txt --- a/llvm/unittests/Analysis/CMakeLists.txt +++ b/llvm/unittests/Analysis/CMakeLists.txt @@ -23,6 +23,7 @@ CaptureTrackingTest.cpp CFGTest.cpp CGSCCPassManagerTest.cpp + ConstraintSystemTest.cpp DDGTest.cpp DivergenceAnalysisTest.cpp DomTreeUpdaterTest.cpp diff --git a/llvm/unittests/Analysis/ConstraintSystemTest.cpp b/llvm/unittests/Analysis/ConstraintSystemTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/Analysis/ConstraintSystemTest.cpp @@ -0,0 +1,82 @@ +//===--- ConstraintSystemTests.cpp ----------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/ConstraintSystem.h" +#include "gtest/gtest.h" + +using namespace llvm; + +namespace { + +TEST(ConstraintSloverTest, TestSolutionChecks) { + { + ConstraintSystem CS; + // x + y <= 10, x >= 5, y >= 6, x <= 10, y <= 10 + CS.addVariableRow({10, 1, 1}); + CS.addVariableRow({-5, -1, 0}); + CS.addVariableRow({-6, 0, -1}); + CS.addVariableRow({10, 1, 0}); + CS.addVariableRow({10, 0, 1}); + + EXPECT_FALSE(CS.mayHaveSolution()); + } + + { + ConstraintSystem CS; + // x + y <= 10, x >= 2, y >= 3, x <= 10, y <= 10 + CS.addVariableRow({10, 1, 1}); + CS.addVariableRow({-2, -1, 0}); + CS.addVariableRow({-3, 0, -1}); + CS.addVariableRow({10, 1, 0}); + CS.addVariableRow({10, 0, 1}); + + EXPECT_TRUE(CS.mayHaveSolution()); + } + + { + ConstraintSystem CS; + // x + y <= 10, 10 >= x, 10 >= y; does not have a solution. + CS.addVariableRow({10, 1, 1}); + CS.addVariableRow({-10, -1, 0}); + CS.addVariableRow({-10, 0, -1}); + + EXPECT_FALSE(CS.mayHaveSolution()); + } + + { + ConstraintSystem CS; + // x + y >= 20, 10 >= x, 10 >= y; does HAVE a solution. + CS.addVariableRow({-20, -1, -1}); + CS.addVariableRow({-10, -1, 0}); + CS.addVariableRow({-10, 0, -1}); + + EXPECT_TRUE(CS.mayHaveSolution()); + } + + { + ConstraintSystem CS; + + // 2x + y + 3z <= 10, 2x + y >= 10, y >= 1 + CS.addVariableRow({10, 2, 1, 3}); + CS.addVariableRow({-10, -2, -1, 0}); + CS.addVariableRow({-1, 0, 0, -1}); + + EXPECT_FALSE(CS.mayHaveSolution()); + } + + { + ConstraintSystem CS; + + // 2x + y + 3z <= 10, 2x + y >= 10 + CS.addVariableRow({10, 2, 1, 3}); + CS.addVariableRow({-10, -2, -1, 0}); + + EXPECT_TRUE(CS.mayHaveSolution()); + } +} +} // namespace