[NFCI][IR] ConstantRangeTest: add basic scaffolding for next-gen precision/correctness testing

[lebedev.ri]

Summary

I have long complained that while we have exhaustive tests
for ConstantRange, they are, uh, not good.

The approach of groking our own constant range
via exhaustive enumeration is, mysterious.

It neither tells us without doubt that the result is
conservatively correct, nor the precise match to the ConstantRange
result tells us that the result is precise.
But yeah, it's fast, i give it that.

In short, there are three things that we need to check:

1. That ConstantRange result is conservatively correct
2. That ConstantRange range is reasonable
3. That ConstantRange result is reasonably precise

So let's not just check the middle one, but all three.

This provides precision test coverage for D88178.

[nikic]

Thanks for putting up the review! I agree that the current testing situation is not ideal, but don't think the approach used here is moving us in the right direction.

It neither tells us without doubt that the result is
conservatively correct, nor the precise match to the ConstantRange
result tells us that the result is precise.

To start with, the current testing code does check for conservative correctness -- the problem is just that it does not check for it separately, so it's not obvious whether a failure is a failure of correctness or a failure of preciseness.

The question of precision is more complicated, because there is no generally applicable notion of a precise range. In many cases the "best" range is the one with the smallest size, but in some cases we also have an explicit sign preference (e.g. for intersection). In D88356 I've put up a more general testing framework that checks correctness and optimality under a preference function. The preference function is something like "smallest" or "smallest non-wrapping", which allows us to precisely specify what it is we're testing for.

This is an alternative to the approach you are proposing here. There's two reasons why I think it is more useful:

• In this patch, you determine precision by counting how many values there are in the value set and how many there are in the range. For the case of the binaryNot() implementation, both of these will coincide for an optimal implementation. However, this is due to a special property of binaryNot() and will not generalize to other operations. In particular, binaryNot() maps a continuous range of values onto another continuous range, so there will be no gaps. In the general case, even an optimal range will contain elements that are not in the exact set. If the precise result set is just two elements 0 and 0x7f then the smallest covering range will still contain 64x more elements than the exact set. So if at the end of the test you get the result that on average, the computed range has 3.7x more elements than the exact set -- what does that actually tell you? Depending on the operation, this could easily be both a very good and a very bad result. For this reason, I don't think value counting is a useful metric in this context.
• This testing approach still retains the need to explicitly specify how the "exact range" is constructed. This is easy for signed/unsigned non-wrapping ranges, but gets tricky for "smallest" ranges, and even trickier if the preference criterion is more complicated than that. The implementation of testBinarySetOperandExhaustive is probably the best example of that: https://github.com/llvm/llvm-project/blob/915310bf14cbac58a81fd60e0fa9dc8d341108e2/llvm/unittests/IR/ConstantRangeTest.cpp#L481 The approach of enumerating all possible ranges and then picking out the best one by preference allows us to move that code onto the normal testing framework.

llvm/unittests/IR/ConstantRangeTest.cpp

 static void ForeachNumInConstantRange(const ConstantRange &CR, Fn TestFn) {
   if (!CR.isEmptySet()) {
     APInt N = CR.getLower();
     do TestFn(N);
     while (++N != CR.getUpper());
   }
 }
 
+unsigned GetNumValuesInConstantRange(const ConstantRange &CR) {
+  unsigned NumValues = 0;
+  ForeachNumInConstantRange(CR, [&NumValues](const APInt &) { ++NumValues; });
+  return NumValues;
+}
+
 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);
   }
 };
 
+struct AccumulatedPrecisionData {
+  unsigned NumActualValues;
+  unsigned NumValuesInActualCR;
+  unsigned NumValuesInExactCR;
+
+  // If NumValuesInActualCR and NumValuesInExactCR are identical, and are not
+  // equal to the NumActualValues, then the implementation is
+  // overly conservatively correct, i.e. imprecise.
+
+  void reset() {
+    NumActualValues = 0;
+    NumValuesInActualCR = 0;
+    NumValuesInExactCR = 0;
+  }
+};
+
+template <typename OpRangeGathererTy, typename Fn1, typename Fn2>
+static void TestUnaryOpExhaustive(Fn1 RangeFn, Fn2 IntFn,
+                                  AccumulatedPrecisionData &Total) {
+  Total.reset();
+
+  constexpr unsigned Bits = 4;
+
+  EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
+    // We'll want to record each true new value, for precision testing.
+    constexpr unsigned NumValuesMax = 1U << Bits;
+    SmallDenseSet<APInt, NumValuesMax> ExactValues;
+
+    // What constant range does ConstantRange method return?
+    ConstantRange ActualCR = RangeFn(CR);
+
+    // We'll want to sanity-check the ActualCR, so this will build our own CR.
+    OpRangeGathererTy ExactR(CR.getBitWidth());
+
+    // Let's iterate for each value in the original constant range.
+    ForeachNumInConstantRange(CR, [&](const APInt &N) {
+      // For this singular value, what is the true new value?
+      const APInt NewN = IntFn(N);
+
+      // Constant range provided by ConstantRange method must be conservatively
+      // correct, it must contain the true new value.
+      EXPECT_TRUE(ActualCR.contains(NewN));
+
+      // Record this true new value in our own constant range.
+      ExactR.account(NewN);
+
+      // And record the new true value itself.
+      ExactValues.insert(NewN);
+    });
+
+    // So, what range did we grok by exhaustively looking over each value?
+    ConstantRange ExactCR = ExactR.getRange();
+
+    // So, how many new values are there actually, and as per the ranges?
+    unsigned NumActualValues = ExactValues.size();
+    unsigned NumValuesInExactCR = GetNumValuesInConstantRange(ExactCR);
+    unsigned NumValuesInActualCR = GetNumValuesInConstantRange(ActualCR);
+
+    // Ranges should contain at least as much values as there actually was,
+    // but it is possible they will contain extras.
+    EXPECT_GE(NumValuesInExactCR, NumActualValues);
+    EXPECT_GE(NumValuesInActualCR, NumActualValues);
+
+    // We expect that OpRangeGathererTy produces the exactly identical range
+    // to what the ConstantRange method does.
+    EXPECT_EQ(ExactR.getRange(), ActualCR);
+
+    // For precision testing, accumulate the overall numbers.
+    Total.NumActualValues += NumActualValues;
+    Total.NumValuesInActualCR += NumValuesInActualCR;
+    Total.NumValuesInExactCR += NumValuesInExactCR;
+  });
+}
+
 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())
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(
+  AccumulatedPrecisionData Precision;
+
+  TestUnaryOpExhaustive<UnsignedOpRangeGatherer>(
       [](const ConstantRange &CR) { return CR.binaryNot(); },
-      [](const APInt &N) { return ~N; });
+      [](const APInt &N) { return ~N; }, Precision);
+  // FIXME: the implementation is not precise.
+  EXPECT_EQ(Precision.NumActualValues, 1936u);
+  EXPECT_EQ(Precision.NumValuesInActualCR, 2496u);
+  EXPECT_EQ(Precision.NumValuesInExactCR, 2496u);
+
   TestUnsignedUnaryOpExhaustive(
       [](const ConstantRange &CR) {
         return CR.binaryXor(
             ConstantRange(APInt::getAllOnesValue(CR.getBitWidth())));
       },
       [](const APInt &N) { return ~N; });
   TestUnsignedUnaryOpExhaustive(
       [](const ConstantRange &CR) {
         return ConstantRange(APInt::getAllOnesValue(CR.getBitWidth()))
             .binaryXor(CR);
       },
       [](const APInt &N) { return ~N; });
 }
 
 }  // anonymous namespace