[LVI] Move LVILatticeVal class to separate header file (NFC).

Summary:
This allows sharing the lattice value code between LVI and SCCP (D36656). 

It also adds a `satisfiesPredicate` function, used by D36656.

Reviewers: davide, sanjoy, efriedma

Reviewed By: sanjoy

Subscribers: mgorny, llvm-commits

Differential Revision: https://reviews.llvm.org/D37591

llvm-svn: 314411

2 files changed, 149 insertions, 0 deletions

diff --git a/llvm/unittests/Analysis/CMakeLists.txt b/llvm/unittests/Analysis/CMakeLists.txt
index ed10ff8a9b0..fabef12126c 100644
--- a/llvm/unittests/Analysis/CMakeLists.txt
+++ b/llvm/unittests/Analysis/CMakeLists.txt
@@ -14,6 +14,7 @@ add_llvm_unittest(AnalysisTests
   CFGTest.cpp
   CGSCCPassManagerTest.cpp
   GlobalsModRefTest.cpp
+  ValueLatticeTest.cpp
   LazyCallGraphTest.cpp
   LoopInfoTest.cpp
   MemoryBuiltinsTest.cpp
diff --git a/llvm/unittests/Analysis/ValueLatticeTest.cpp b/llvm/unittests/Analysis/ValueLatticeTest.cpp
new file mode 100644
index 00000000000..3e410256414
--- /dev/null
+++ b/llvm/unittests/Analysis/ValueLatticeTest.cpp
@@ -0,0 +1,148 @@
+//===- ValueLatticeTest.cpp - ScalarEvolution unit tests --------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/ValueLattice.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/ConstantRange.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+namespace {
+
+// We use this fixture to ensure that we clean up ScalarEvolution before
+// deleting the PassManager.
+class ValueLatticeTest : public testing::Test {
+protected:
+  LLVMContext Context;
+  Module M;
+
+  ValueLatticeTest() : M("", Context) {}
+};
+
+TEST_F(ValueLatticeTest, ValueLatticeGetters) {
+  auto I32Ty = IntegerType::get(Context, 32);
+  auto *C1 = ConstantInt::get(I32Ty, 1);
+
+  EXPECT_TRUE(ValueLatticeElement::get(C1).isConstantRange());
+  EXPECT_TRUE(
+      ValueLatticeElement::getRange({C1->getValue()}).isConstantRange());
+  EXPECT_TRUE(ValueLatticeElement::getOverdefined().isOverdefined());
+
+  auto FloatTy = Type::getFloatTy(Context);
+  auto *C2 = ConstantFP::get(FloatTy, 1.1);
+  EXPECT_TRUE(ValueLatticeElement::get(C2).isConstant());
+  EXPECT_TRUE(ValueLatticeElement::getNot(C2).isNotConstant());
+}
+
+TEST_F(ValueLatticeTest, MergeIn) {
+  auto I32Ty = IntegerType::get(Context, 32);
+  auto *C1 = ConstantInt::get(I32Ty, 1);
+
+  // Merge to lattice values with equal integer constant.
+  auto LV1 = ValueLatticeElement::get(C1);
+  LV1.mergeIn(ValueLatticeElement::get(C1), M.getDataLayout());
+  EXPECT_TRUE(LV1.isConstantRange());
+  EXPECT_EQ(LV1.asConstantInteger().getValue().getLimitedValue(), 1U);
+
+  // Merge LV1 with different integer constant.
+  LV1.mergeIn(ValueLatticeElement::get(ConstantInt::get(I32Ty, 99)),
+              M.getDataLayout());
+  EXPECT_TRUE(LV1.isConstantRange());
+  EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 1U);
+  EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 100U);
+
+  // Merge LV1 in undefined value.
+  ValueLatticeElement LV2;
+  LV2.mergeIn(LV1, M.getDataLayout());
+  EXPECT_TRUE(LV1.isConstantRange());
+  EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 1U);
+  EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 100U);
+  EXPECT_TRUE(LV2.isConstantRange());
+  EXPECT_EQ(LV2.getConstantRange().getLower().getLimitedValue(), 1U);
+  EXPECT_EQ(LV2.getConstantRange().getUpper().getLimitedValue(), 100U);
+
+  // Merge with overdefined.
+  LV1.mergeIn(ValueLatticeElement::getOverdefined(), M.getDataLayout());
+  EXPECT_TRUE(LV1.isOverdefined());
+}
+
+TEST_F(ValueLatticeTest, satisfiesPredicateIntegers) {
+  auto I32Ty = IntegerType::get(Context, 32);
+  auto *C1 = ConstantInt::get(I32Ty, 1);
+  auto LV1 = ValueLatticeElement::get(C1);
+
+  // Check satisfiesPredicate for equal integer constants.
+  EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_EQ, LV1));
+  EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_SGE, LV1));
+  EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_SLE, LV1));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_NE, LV1));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_SLT, LV1));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_SGT, LV1));
+
+  auto LV2 =
+      ValueLatticeElement::getRange({APInt(32, 10, true), APInt(32, 20, true)});
+  // Check satisfiesPredicate with distinct integer ranges.
+  EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_SLT, LV2));
+  EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_SLE, LV2));
+  EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_NE, LV2));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_EQ, LV2));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_SGE, LV2));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_SGT, LV2));
+
+  auto LV3 =
+      ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 19, true)});
+  // Check satisfiesPredicate with a subset integer ranges.
+  EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_SLT, LV3));
+  EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_SLE, LV3));
+  EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_NE, LV3));
+  EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_EQ, LV3));
+  EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_SGE, LV3));
+  EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_SGT, LV3));
+
+  auto LV4 =
+      ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 25, true)});
+  // Check satisfiesPredicate with overlapping integer ranges.
+  EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_SLT, LV4));
+  EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_SLE, LV4));
+  EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_NE, LV4));
+  EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_EQ, LV4));
+  EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_SGE, LV4));
+  EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_SGT, LV4));
+}
+
+TEST_F(ValueLatticeTest, satisfiesPredicateFloat) {
+  auto FloatTy = IntegerType::getFloatTy(Context);
+  auto *C1 = ConstantFP::get(FloatTy, 1.0);
+  auto LV1 = ValueLatticeElement::get(C1);
+  auto LV2 = ValueLatticeElement::get(C1);
+
+  // Check satisfiesPredicate for equal floating point constants.
+  EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::FCMP_OEQ, LV2));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OGE, LV2));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OLE, LV2));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_ONE, LV2));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OLT, LV2));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OGT, LV2));
+
+  LV1.mergeIn(ValueLatticeElement::get(ConstantFP::get(FloatTy, 2.2)),
+              M.getDataLayout());
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OEQ, LV2));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OGE, LV2));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OLE, LV2));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_ONE, LV2));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OLT, LV2));
+  EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OGT, LV2));
+}
+
+} // end anonymous namespace
+} // end namespace llvm