[ConstantRange] Make exhaustive testing more principled (NFC)

[nikic]

Summary

The current infrastructure for exhaustive ConstantRange testing is somewhat confusing in what exactly it tests (D88283) and currently cannot even be used for operations that produce smallest-size results, rather than signed/unsigned approximations.

This patch tries to make the testing more principled by collecting the exact set of results of an operation into a bit set and then comparing it against the range approximation by:

• Checking conservative correctness: All elements in the set must be in the range.
• Checking optimality under a given preference function: None of the (slack-free) ranges that can be constructed from the set are preferred over the computed range.

Implemented preference functions are:

• PreferSmallest: Smallest range regardless of signed/unsigned wrapping behavior. Probably what we would call "optimal" without further qualification.
• PreferSmallestUnsigned/Signed: Smallest range that has no unsigned/signed wrapping. We use this if our calculation is precise only up to signed/unsigned envelope.
• PreferSmallestNonFullUnsigned/Signed: Smallest range that has no unsigned/signed wrapping -- but preferring a smaller wrapping range over a (non-wrapping) full range. We use this if we have a fully precise calculation but apply a sign preference to the result (union/intersection). Even with a sign preference, returning a wrapping range is still "strictly better" than returning a full one.

[nikic]

Use preference function instead of filter function, making the testing approach more broadly applicable.

[nikic]

Simplify implementation. There's no need to collect all the best ranges explicitly.

[nikic]

@lebedev.ri Any thoughts on this testing approach relative to what we do currently and your proposal at D88283? I thought this was quite nice in how it brings everything under one umbrella, including cases we could not test before (add, sub) or only with a lot of effort (testBinarySetOperationExhaustive), but I'm not sure it addresses your concerns.

[nikic]

Rebase

[nikic]

Ping :) I'd also be happy with an "I don't really care", as I'm not really looking for technical review for testing changes. Just want to make sure I'm not stepping on any toes, as you also did work in this area.

llvm/unittests/IR/ConstantRangeTest.cpp

 //===- ConstantRangeTest.cpp - ConstantRange tests ------------------------===//
 //
 // 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/ADT/BitVector.h"
+#include "llvm/ADT/SmallBitVector.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Support/KnownBits.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {

 static void ForeachNumInConstantRange(const ConstantRange &CR, Fn TestFn) {
   if (!CR.isEmptySet()) {
     APInt N = CR.getLower();
     do TestFn(N);
     while (++N != CR.getUpper());
   }
 }
 
+static unsigned GetRangeSize(const ConstantRange &CR) {
+  if (CR.isFullSet())
+    return 1 << CR.getBitWidth();
+  return (CR.getUpper() - CR.getLower()).getZExtValue();
+}
+
+using FilterFn = llvm::function_ref<bool(const ConstantRange &)>;
+
+bool FilterUnsigned(const ConstantRange &CR) {
+  return !CR.isWrappedSet();
+}
+
+bool FilterSigned(const ConstantRange &CR) {
+  return !CR.isSignWrappedSet();
+}
+
+bool FilterAll(const ConstantRange &) {
+  return true;
+}
+
+// Check whether constant range CR is an optimal approximation of the set
+// Elems if only ranges satisfying RangeFilter are considered. This function
+// checks both correctness (all elements in Elems must be in CR) and
+// size-optimality (CR must be one of the smallest ranges that both contain
+// all Elems and satisfy RangeFilter).
+static void TestRange(const ConstantRange &CR, const SmallBitVector &Elems,
+                      FilterFn RangeFilter) {
+  unsigned BitWidth = CR.getBitWidth();
+
+  // Check conservative correctness.
+  for (unsigned Elem : Elems.set_bits()) {
+    EXPECT_TRUE(CR.contains(APInt(BitWidth, Elem)));
+  }
+
+  // Make sure we have at least two elements for the code below.
+  if (Elems.none()) {
+    EXPECT_TRUE(CR.isEmptySet());
+    return;
+  }
+
+  if (Elems.count() == 1) {
+    EXPECT_TRUE(CR.isSingleElement());
+    return;
+  }
+
+  // Look at all pairs of adjacent elements and the slack-free ranges
+  // [Elem, PrevElem] they imply. For ranges allowed by RangeFilter, check if
+  // CR matches at least one, and find smallest range size.
+  unsigned SmallestRangeSize = UINT_MAX;
+  bool FoundMatchingRange = false;
+  int FirstElem = Elems.find_first();
+  int PrevElem = FirstElem, Elem;
+  do {
+    Elem = Elems.find_next(PrevElem);
+    if (Elem < 0)
+      Elem = FirstElem; // Wrap around to first element.
+
+    ConstantRange PossibleCR =
+        ConstantRange::getNonEmpty(APInt(BitWidth, Elem),
+                                   APInt(BitWidth, PrevElem) + 1);
+
+    // Only consider ranges allowed by the filter function.
+    if (RangeFilter(PossibleCR)) {
+      FoundMatchingRange |= PossibleCR == CR;
+      SmallestRangeSize = std::min(SmallestRangeSize, GetRangeSize(PossibleCR));
+    }
+
+    PrevElem = Elem;
+  } while (Elem != FirstElem);
+
+  // Our range must be the same as one of the possible ranges.
+  EXPECT_TRUE(FoundMatchingRange);
+
+  // Additionally, it must have the smallest possible size (though there may
+  // be multipple ranges with the same size).
+  EXPECT_EQ(SmallestRangeSize, GetRangeSize(CR));
+}
+
+using UnaryRangeFn = llvm::function_ref<ConstantRange(const ConstantRange &)>;
+using UnaryIntFn = llvm::function_ref<Optional<APInt>(const APInt &)>;
+
+static void TestUnaryOpExhaustive(UnaryRangeFn RangeFn, UnaryIntFn IntFn,
+                                  FilterFn RangeFilter = FilterAll) {
+  unsigned Bits = 4;
+  EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
+    SmallBitVector Elems(1 << Bits);
+    ForeachNumInConstantRange(CR, [&](const APInt &N) {
+      if (Optional<APInt> ResultN = IntFn(N))
+        Elems.set(ResultN->getZExtValue());
+    });
+    TestRange(RangeFn(CR), Elems, RangeFilter);
+  });
+}
+
+using BinaryRangeFn = llvm::function_ref<ConstantRange(const ConstantRange &,
+                                                       const ConstantRange &)>;
+using BinaryIntFn = llvm::function_ref<Optional<APInt>(const APInt &,
+                                                       const APInt &)>;
+
+static void TestBinaryOpExhaustive(BinaryRangeFn RangeFn, BinaryIntFn IntFn,
+                                   FilterFn RangeFilter = FilterAll) {
+  unsigned Bits = 4;
+  EnumerateTwoConstantRanges(
+      Bits, [&](const ConstantRange &CR1, const ConstantRange &CR2) {
+        SmallBitVector Elems(1 << Bits);
+        ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
+          ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
+            if (Optional<APInt> ResultN = IntFn(N1, N2))
+              Elems.set(ResultN->getZExtValue());
+          });
+        });
+        TestRange(RangeFn(CR1, CR2), Elems, RangeFilter);
+      });
+}
+
+static void TestBinaryOpExhaustiveCorrectnessOnly(BinaryRangeFn RangeFn,
+                                                  BinaryIntFn IntFn) {
+  unsigned Bits = 4;
+  EnumerateTwoConstantRanges(
+      Bits, [&](const ConstantRange &CR1, const ConstantRange &CR2) {
+        ConstantRange ResultCR = RangeFn(CR1, CR2);
+        ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
+          ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
+            if (Optional<APInt> ResultN = IntFn(N1, N2)) {
+              EXPECT_TRUE(ResultCR.contains(*ResultN));
+            }
+          });
+        });
+      });
+}
+
 struct OpRangeGathererBase {
   void account(const APInt &N);
   ConstantRange getRange();
 };
 
 struct UnsignedOpRangeGatherer : public OpRangeGathererBase {
   APInt Min;
   APInt Max;
struct SignedOpRangeGatherer : public OpRangeGathererBase {
 
   ConstantRange getRange() {
     if (Min.sgt(Max))
       return ConstantRange::getEmpty(Min.getBitWidth());
     return ConstantRange::getNonEmpty(Min, Max + 1);
   }
 };
 
-template <typename Fn1, typename Fn2>
-static void TestUnsignedUnaryOpExhaustive(Fn1 RangeFn, Fn2 IntFn,
-                                          bool SkipSignedIntMin = false) {
-  unsigned Bits = 4;
-  EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
-    UnsignedOpRangeGatherer R(CR.getBitWidth());
-    ForeachNumInConstantRange(CR, [&](const APInt &N) {
-      if (SkipSignedIntMin && N.isMinSignedValue())
-        return;
-      R.account(IntFn(N));
-    });
-
-    ConstantRange ExactCR = R.getRange();
-    ConstantRange ActualCR = RangeFn(CR);
-
-    EXPECT_EQ(ExactCR, ActualCR);
-  });
-}
-
-template <typename Fn1, typename Fn2>
-static void TestUnsignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn,
-                                        bool SkipZeroRHS = false,
-                                        bool CorrectnessOnly = false) {
-  unsigned Bits = 4;
-  EnumerateTwoConstantRanges(
-      Bits, [&](const ConstantRange &CR1, const ConstantRange &CR2) {
-        UnsignedOpRangeGatherer R(CR1.getBitWidth());
-        ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
-          ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
-            if (SkipZeroRHS && N2 == 0)
-              return;
-            R.account(IntFn(N1, N2));
-          });
-        });
-
-        ConstantRange CR = RangeFn(CR1, CR2);
-
-        ConstantRange Exact = R.getRange();
-
-        if (!CorrectnessOnly) {
-          EXPECT_EQ(Exact, CR);
-          return;
-        }
-
-        EXPECT_TRUE(CR.contains(Exact));
-        if (Exact.isEmptySet())
-          EXPECT_TRUE(CR.isEmptySet());
-      });
-}
-
-template <typename Fn1, typename Fn2>
-static void TestSignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn,
-                                      bool SkipZeroRHS = false,
-                                      bool CorrectnessOnly = false) {
-  unsigned Bits = 4;
-  EnumerateTwoConstantRanges(
-      Bits, [&](const ConstantRange &CR1, const ConstantRange &CR2) {
-        SignedOpRangeGatherer R(CR1.getBitWidth());
-        ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
-          ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
-            if (SkipZeroRHS && N2 == 0)
-              return;
-
-            R.account(IntFn(N1, N2));
-          });
-        });
-
-        ConstantRange CR = RangeFn(CR1, CR2);
-
-        ConstantRange Exact = R.getRange();
-        if (CorrectnessOnly) {
-          EXPECT_TRUE(CR.contains(Exact));
-        } else {
-          EXPECT_EQ(Exact, CR);
-        }
-      });
-}
-
 ConstantRange ConstantRangeTest::Full(16, true);
 ConstantRange ConstantRangeTest::Empty(16, false);
 ConstantRange ConstantRangeTest::One(APInt(16, 0xa));
 ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));
 ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));
 
 TEST_F(ConstantRangeTest, Basics) {
   EXPECT_TRUE(Full.isFullSet());
TEST_F(ConstantRangeTest, Add) {
   EXPECT_EQ(Empty.add(Wrap), Empty);
   EXPECT_EQ(Empty.add(APInt(16, 4)), Empty);
   EXPECT_EQ(Some.add(APInt(16, 4)),
             ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
   EXPECT_EQ(Wrap.add(APInt(16, 4)),
             ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
   EXPECT_EQ(One.add(APInt(16, 4)),
             ConstantRange(APInt(16, 0xe)));
+
+  TestBinaryOpExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.add(CR2);
+      },
+      [](const APInt &N1, const APInt &N2) {
+        return N1 + N2;
+      });
 }
 
 template <typename Fn1, typename Fn2>
 static void TestAddWithNoSignedWrapExhaustive(Fn1 RangeFn, Fn2 IntFn) {
   unsigned Bits = 4;
   EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
                                        const ConstantRange &CR2) {
     ConstantRange CR = RangeFn(CR1, CR2);
TEST_F(ConstantRangeTest, Sub) {
   EXPECT_EQ(Some.sub(APInt(16, 4)),
             ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
   EXPECT_EQ(Some.sub(Some),
             ConstantRange(APInt(16, 0xf561), APInt(16, 0xaa0)));
   EXPECT_EQ(Wrap.sub(APInt(16, 4)),
             ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
   EXPECT_EQ(One.sub(APInt(16, 4)),
             ConstantRange(APInt(16, 0x6)));
+
+  TestBinaryOpExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.sub(CR2);
+      },
+      [](const APInt &N1, const APInt &N2) {
+        return N1 - N2;
+      });
 }
 
 TEST_F(ConstantRangeTest, SubWithNoWrap) {
   typedef OverflowingBinaryOperator OBO;
   TestAddWithNoSignedWrapExhaustive(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.subWithNoWrap(CR2, OBO::NoSignedWrap);
       },
TEST_F(ConstantRangeTest, URem) {
   EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
                 .urem(ConstantRange(APInt(16, 19), APInt(16, 30))),
             ConstantRange(APInt(16, 0), APInt(16, 20)));
   // [12, 14] % 10 is [2, 4], but we conservatively compute [0, 9].
   EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
                 .urem(ConstantRange(APInt(16, 10))),
             ConstantRange(APInt(16, 0), APInt(16, 10)));
 
-  TestUnsignedBinOpExhaustive(
+  TestBinaryOpExhaustiveCorrectnessOnly(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.urem(CR2);
       },
-      [](const APInt &N1, const APInt &N2) {
+      [](const APInt &N1, const APInt &N2) -> Optional<APInt> {
+        if (N2.isNullValue())
+          return None;
         return N1.urem(N2);
-      },
-      /* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
+      });
 }
 
 TEST_F(ConstantRangeTest, SRem) {
   EXPECT_EQ(Full.srem(Empty), Empty);
   EXPECT_EQ(Empty.srem(Full), Empty);
   // srem by zero is UB.
   EXPECT_EQ(Full.srem(ConstantRange(APInt(16, 0))), Empty);
   // srem by full range doesn't contain SignedMinValue.
TEST_F(ConstantRangeTest, SRem) {
   EXPECT_EQ(PosNegSmallLHS.srem(IntMinMod), PosNegSmallLHS);
 
   // Example of a suboptimal result:
   // [12, 14] srem 10 is [2, 4], but we conservatively compute [0, 9].
   EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
                 .srem(ConstantRange(APInt(16, 10))),
             ConstantRange(APInt(16, 0), APInt(16, 10)));
 
-  TestSignedBinOpExhaustive(
+  TestBinaryOpExhaustiveCorrectnessOnly(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.srem(CR2);
       },
-      [](const APInt &N1, const APInt &N2) {
+      [](const APInt &N1, const APInt &N2) -> Optional<APInt> {
+        if (N2.isNullValue())
+          return None;
         return N1.srem(N2);
-      },
-      /* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
+      });
 }
 
 TEST_F(ConstantRangeTest, Shl) {
   ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000));
   ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0));
   EXPECT_EQ(Full.shl(Full), Full);
   EXPECT_EQ(Full.shl(Empty), Empty);
   EXPECT_EQ(Full.shl(One), Full);    // TODO: [0, (-1 << 0xa) + 1)
assert((CR.isEmptySet() || !AllNegative || !AllNonNegative) &&
            "Only empty set can be both all negative and all non-negative");
 
     EXPECT_EQ(AllNegative, CR.isAllNegative());
     EXPECT_EQ(AllNonNegative, CR.isAllNonNegative());
   });
 }
 
 TEST_F(ConstantRangeTest, UAddSat) {
-  TestUnsignedBinOpExhaustive(
+  TestBinaryOpExhaustive(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.uadd_sat(CR2);
       },
       [](const APInt &N1, const APInt &N2) {
         return N1.uadd_sat(N2);
-      });
+      },
+      FilterUnsigned);
 }
 
 TEST_F(ConstantRangeTest, USubSat) {
-  TestUnsignedBinOpExhaustive(
+  TestBinaryOpExhaustive(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.usub_sat(CR2);
       },
       [](const APInt &N1, const APInt &N2) {
         return N1.usub_sat(N2);
-      });
+      },
+      FilterUnsigned);
 }
 
 TEST_F(ConstantRangeTest, UMulSat) {
-  TestUnsignedBinOpExhaustive(
+  TestBinaryOpExhaustive(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.umul_sat(CR2);
       },
-      [](const APInt &N1, const APInt &N2) { return N1.umul_sat(N2); });
+      [](const APInt &N1, const APInt &N2) { return N1.umul_sat(N2); },
+      FilterUnsigned);
 }
 
 TEST_F(ConstantRangeTest, UShlSat) {
-  TestUnsignedBinOpExhaustive(
+  TestBinaryOpExhaustive(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.ushl_sat(CR2);
       },
-      [](const APInt &N1, const APInt &N2) { return N1.ushl_sat(N2); });
+      [](const APInt &N1, const APInt &N2) { return N1.ushl_sat(N2); },
+      FilterUnsigned);
 }
 
 TEST_F(ConstantRangeTest, SAddSat) {
-  TestSignedBinOpExhaustive(
+  TestBinaryOpExhaustive(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.sadd_sat(CR2);
       },
       [](const APInt &N1, const APInt &N2) {
         return N1.sadd_sat(N2);
-      });
+      },
+      FilterSigned);
 }
 
 TEST_F(ConstantRangeTest, SSubSat) {
-  TestSignedBinOpExhaustive(
+  TestBinaryOpExhaustive(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.ssub_sat(CR2);
       },
       [](const APInt &N1, const APInt &N2) {
         return N1.ssub_sat(N2);
-      });
+      },
+      FilterSigned);
 }
 
 TEST_F(ConstantRangeTest, SMulSat) {
-  TestSignedBinOpExhaustive(
+  TestBinaryOpExhaustive(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.smul_sat(CR2);
       },
-      [](const APInt &N1, const APInt &N2) { return N1.smul_sat(N2); });
+      [](const APInt &N1, const APInt &N2) { return N1.smul_sat(N2); },
+      FilterSigned);
 }
 
 TEST_F(ConstantRangeTest, SShlSat) {
-  TestSignedBinOpExhaustive(
+  TestBinaryOpExhaustive(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.sshl_sat(CR2);
       },
-      [](const APInt &N1, const APInt &N2) { return N1.sshl_sat(N2); });
+      [](const APInt &N1, const APInt &N2) { return N1.sshl_sat(N2); },
+      FilterSigned);
 }
 
 TEST_F(ConstantRangeTest, Abs) {
-  // We're working with unsigned integers here, because it makes the signed
-  // min case non-wrapping.
-  TestUnsignedUnaryOpExhaustive(
+  TestUnaryOpExhaustive(
       [](const ConstantRange &CR) { return CR.abs(); },
       [](const APInt &N) { return N.abs(); });
 
-  TestUnsignedUnaryOpExhaustive(
+  TestUnaryOpExhaustive(
       [](const ConstantRange &CR) { return CR.abs(/*IntMinIsPoison=*/true); },
-      [](const APInt &N) { return N.abs(); },
-      /*SkipSignedIntMin=*/true);
+      [](const APInt &N) -> Optional<APInt> {
+        if (N.isMinSignedValue())
+          return None;
+        return N.abs();
+      });
 }
 
 TEST_F(ConstantRangeTest, castOps) {
   ConstantRange A(APInt(16, 66), APInt(16, 128));
   ConstantRange FpToI8 = A.castOp(Instruction::FPToSI, 8);
   EXPECT_EQ(8u, FpToI8.getBitWidth());
   EXPECT_TRUE(FpToI8.isFullSet());
 
TEST_F(ConstantRangeTest, binaryXor) {
   ConstantRange R16_35(APInt(8, 16), APInt(8, 35));
   ConstantRange R0_99(APInt(8, 0), APInt(8, 99));
   EXPECT_TRUE(R16_35.binaryXor(R16_35).isFullSet());
   EXPECT_TRUE(R16_35.binaryXor(R0_99).isFullSet());
   EXPECT_TRUE(R0_99.binaryXor(R16_35).isFullSet());
 }
 
 TEST_F(ConstantRangeTest, binaryNot) {
-  TestUnsignedUnaryOpExhaustive(
+  // TODO: Improve binaryNot() implement to remove the need for FilterUnsigned.
+  TestUnaryOpExhaustive(
       [](const ConstantRange &CR) { return CR.binaryNot(); },
-      [](const APInt &N) { return ~N; });
-  TestUnsignedUnaryOpExhaustive(
+      [](const APInt &N) { return ~N; },
+      FilterUnsigned);
+  TestUnaryOpExhaustive(
       [](const ConstantRange &CR) {
         return CR.binaryXor(
             ConstantRange(APInt::getAllOnesValue(CR.getBitWidth())));
       },
-      [](const APInt &N) { return ~N; });
-  TestUnsignedUnaryOpExhaustive(
+      [](const APInt &N) { return ~N; },
+      FilterUnsigned);
+  TestUnaryOpExhaustive(
       [](const ConstantRange &CR) {
         return ConstantRange(APInt::getAllOnesValue(CR.getBitWidth()))
             .binaryXor(CR);
       },
-      [](const APInt &N) { return ~N; });
+      [](const APInt &N) { return ~N; },
+      FilterUnsigned);
 }
 
 }  // anonymous namespace