[ConstantRangeTest] Make exhaustive testing more principled (NFC)
authorNikita Popov <nikita.ppv@gmail.com>
Wed, 23 Sep 2020 18:43:59 +0000 (20:43 +0200)
committerNikita Popov <nikita.ppv@gmail.com>
Sat, 20 Feb 2021 11:37:31 +0000 (12:37 +0100)
commit2b729548f00bcab8c4dc6967bca0e6661324f27e
treea9e22903706fefa40c6d4affbef1c0ad5ab5163b
parent7c31661b224ae44a42c9bd5fdcb60aee986e416a
[ConstantRangeTest] Make exhaustive testing more principled (NFC)

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

This patch makes 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.

This also addresses PR49273 by replacing the fragile manual range
construction logic in testBinarySetOperationExhaustive() with generic
code that isn't specialized to the particular form of ranges that set
operations can produces.

Differential Revision: https://reviews.llvm.org/D88356
llvm/unittests/IR/ConstantRangeTest.cpp