aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAldy Hernandez <aldyh@gcc.gnu.org>2019-08-22 11:01:15 +0000
committerAldy Hernandez <aldyh@gcc.gnu.org>2019-08-22 11:01:15 +0000
commit48fdfe82de94aafc349cdbf8988b7271b6589e29 (patch)
treecd9b3fa915a71566bb495daaec307a53fc200ed4
parent9018589c64aa70eaf599ac33352b03faa1644a25 (diff)
downloadgcc-48fdfe82de94aafc349cdbf8988b7271b6589e29.zip
gcc-48fdfe82de94aafc349cdbf8988b7271b6589e29.tar.gz
gcc-48fdfe82de94aafc349cdbf8988b7271b6589e29.tar.bz2
Move range self tests to range-op.cc.
From-SVN: r274819
-rw-r--r--gcc/range-op.cc514
-rw-r--r--gcc/range.cc518
2 files changed, 514 insertions, 518 deletions
diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 6a96c24..de6f236 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -2215,3 +2215,517 @@ range_cast (irange &r, tree type)
range_operator *op = range_op_handler (CONVERT_EXPR, type);
r = op->fold_range (type, r, irange (type));
}
+
+#if CHECKING_P
+#include "selftest.h"
+#include "stor-layout.h"
+
+// Ideally this should go in namespace selftest, but range_tests
+// needs to be a friend of class irange so it can access
+// irange::m_max_pairs.
+
+#define INT(N) build_int_cst (integer_type_node, (N))
+#define UINT(N) build_int_cstu (unsigned_type_node, (N))
+#define INT16(N) build_int_cst (short_integer_type_node, (N))
+#define UINT16(N) build_int_cstu (short_unsigned_type_node, (N))
+#define INT64(N) build_int_cstu (long_long_integer_type_node, (N))
+#define UINT64(N) build_int_cstu (long_long_unsigned_type_node, (N))
+#define UINT128(N) build_int_cstu (u128_type, (N))
+#define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
+#define SCHAR(N) build_int_cst (signed_char_type_node, (N))
+
+#define RANGE3(A,B,C,D,E,F) \
+( i1 = irange (INT (A), INT (B)), \
+ i2 = irange (INT (C), INT (D)), \
+ i3 = irange (INT (E), INT (F)), \
+ i1.union_ (i2), \
+ i1.union_ (i3), \
+ i1 )
+
+// Run all of the selftests within this file.
+
+void
+range_tests ()
+{
+ tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
+ irange i1, i2, i3;
+ irange r0, r1, rold;
+
+ // Test that NOT(255) is [0..254] in 8-bit land.
+ irange not_255 (VR_ANTI_RANGE, UCHAR (255), UCHAR (255));
+ ASSERT_TRUE (not_255 == irange (UCHAR (0), UCHAR (254)));
+
+ // Test that NOT(0) is [1..255] in 8-bit land.
+ irange not_zero = range_nonzero (unsigned_char_type_node);
+ ASSERT_TRUE (not_zero == irange (UCHAR (1), UCHAR (255)));
+
+ // Check that [0,127][0x..ffffff80,0x..ffffff]
+ // => ~[128, 0x..ffffff7f].
+ r0 = irange (UINT128 (0), UINT128 (127));
+ tree high = build_minus_one_cst (u128_type);
+ // low = -1 - 127 => 0x..ffffff80.
+ tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127));
+ r1 = irange (low, high); // [0x..ffffff80, 0x..ffffffff]
+ // r0 = [0,127][0x..ffffff80,0x..fffffff].
+ r0.union_ (r1);
+ // r1 = [128, 0x..ffffff7f].
+ r1 = irange (UINT128(128),
+ fold_build2 (MINUS_EXPR, u128_type,
+ build_minus_one_cst (u128_type),
+ UINT128(128)));
+ r0.invert ();
+ ASSERT_TRUE (r0 == r1);
+
+ r0.set_varying (integer_type_node);
+ tree minint = wide_int_to_tree (integer_type_node, r0.lower_bound ());
+ tree maxint = wide_int_to_tree (integer_type_node, r0.upper_bound ());
+
+ r0.set_varying (short_integer_type_node);
+ tree minshort = wide_int_to_tree (short_integer_type_node, r0.lower_bound ());
+ tree maxshort = wide_int_to_tree (short_integer_type_node, r0.upper_bound ());
+
+ r0.set_varying (unsigned_type_node);
+ tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ());
+
+ // Check that ~[0,5] => [6,MAX] for unsigned int.
+ r0 = irange (UINT (0), UINT (5));
+ r0.invert ();
+ ASSERT_TRUE (r0 == irange (UINT(6), maxuint));
+
+ // Check that ~[10,MAX] => [0,9] for unsigned int.
+ r0 = irange (VR_RANGE, UINT(10), maxuint);
+ r0.invert ();
+ ASSERT_TRUE (r0 == irange (UINT (0), UINT (9)));
+
+ // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
+ r0 = irange (VR_ANTI_RANGE, UINT128 (0), UINT128 (5));
+ r1 = irange (UINT128(6), build_minus_one_cst (u128_type));
+ ASSERT_TRUE (r0 == r1);
+
+ // Check that [~5] is really [-MIN,4][6,MAX].
+ r0 = irange (VR_ANTI_RANGE, INT (5), INT (5));
+ r1 = irange (minint, INT (4));
+ r1.union_ (irange (INT (6), maxint));
+ ASSERT_FALSE (r1.undefined_p ());
+ ASSERT_TRUE (r0 == r1);
+
+ r1 = irange (INT (5), INT (5));
+ r1.check ();
+ irange r2 (r1);
+ ASSERT_TRUE (r1 == r2);
+
+ r1 = irange (INT (5), INT (10));
+ r1.check ();
+
+ r1 = irange (integer_type_node,
+ wi::to_wide (INT (5)), wi::to_wide (INT (10)));
+ r1.check ();
+ ASSERT_TRUE (r1.contains_p (INT (7)));
+
+ r1 = irange (SCHAR (0), SCHAR (20));
+ ASSERT_TRUE (r1.contains_p (SCHAR(15)));
+ ASSERT_FALSE (r1.contains_p (SCHAR(300)));
+
+ // If a range is in any way outside of the range for the converted
+ // to range, default to the range for the new type.
+ r1 = irange (integer_zero_node, maxint);
+ range_cast (r1, short_integer_type_node);
+ ASSERT_TRUE (r1.lower_bound () == wi::to_wide (minshort)
+ && r1.upper_bound() == wi::to_wide (maxshort));
+
+ // (unsigned char)[-5,-1] => [251,255].
+ r0 = rold = irange (SCHAR (-5), SCHAR (-1));
+ range_cast (r0, unsigned_char_type_node);
+ ASSERT_TRUE (r0 == irange (UCHAR (251), UCHAR (255)));
+ range_cast (r0, signed_char_type_node);
+ ASSERT_TRUE (r0 == rold);
+
+ // (signed char)[15, 150] => [-128,-106][15,127].
+ r0 = rold = irange (UCHAR (15), UCHAR (150));
+ range_cast (r0, signed_char_type_node);
+ r1 = irange (SCHAR (15), SCHAR (127));
+ r2 = irange (SCHAR (-128), SCHAR (-106));
+ r1.union_ (r2);
+ ASSERT_TRUE (r1 == r0);
+ range_cast (r0, unsigned_char_type_node);
+ ASSERT_TRUE (r0 == rold);
+
+ // (unsigned char)[-5, 5] => [0,5][251,255].
+ r0 = rold = irange (SCHAR (-5), SCHAR (5));
+ range_cast (r0, unsigned_char_type_node);
+ r1 = irange (UCHAR (251), UCHAR (255));
+ r2 = irange (UCHAR (0), UCHAR (5));
+ r1.union_ (r2);
+ ASSERT_TRUE (r0 == r1);
+ range_cast (r0, signed_char_type_node);
+ ASSERT_TRUE (r0 == rold);
+
+ // (unsigned char)[-5,5] => [0,5][251,255].
+ r0 = irange (INT (-5), INT (5));
+ range_cast (r0, unsigned_char_type_node);
+ r1 = irange (UCHAR (0), UCHAR (5));
+ r1.union_ (irange (UCHAR (251), UCHAR (255)));
+ ASSERT_TRUE (r0 == r1);
+
+ // (unsigned char)[5U,1974U] => [0,255].
+ r0 = irange (UINT (5), UINT (1974));
+ range_cast (r0, unsigned_char_type_node);
+ ASSERT_TRUE (r0 == irange (UCHAR (0), UCHAR (255)));
+ range_cast (r0, integer_type_node);
+ // Going to a wider range should not sign extend.
+ ASSERT_TRUE (r0 == irange (INT (0), INT (255)));
+
+ // (unsigned char)[-350,15] => [0,255].
+ r0 = irange (INT (-350), INT (15));
+ range_cast (r0, unsigned_char_type_node);
+ ASSERT_TRUE (r0 == irange (TYPE_MIN_VALUE (unsigned_char_type_node),
+ TYPE_MAX_VALUE (unsigned_char_type_node)));
+
+ // Casting [-120,20] from signed char to unsigned short.
+ // => [0, 20][0xff88, 0xffff].
+ r0 = irange (SCHAR (-120), SCHAR (20));
+ range_cast (r0, short_unsigned_type_node);
+ r1 = irange (UINT16 (0), UINT16 (20));
+ r2 = irange (UINT16 (0xff88), UINT16 (0xffff));
+ r1.union_ (r2);
+ ASSERT_TRUE (r0 == r1);
+ // A truncating cast back to signed char will work because [-120, 20]
+ // is representable in signed char.
+ range_cast (r0, signed_char_type_node);
+ ASSERT_TRUE (r0 == irange (SCHAR (-120), SCHAR (20)));
+
+ // unsigned char -> signed short
+ // (signed short)[(unsigned char)25, (unsigned char)250]
+ // => [(signed short)25, (signed short)250]
+ r0 = rold = irange (UCHAR (25), UCHAR (250));
+ range_cast (r0, short_integer_type_node);
+ r1 = irange (INT16 (25), INT16 (250));
+ ASSERT_TRUE (r0 == r1);
+ range_cast (r0, unsigned_char_type_node);
+ ASSERT_TRUE (r0 == rold);
+
+ // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned.
+ r0 = irange (TYPE_MIN_VALUE (long_long_integer_type_node),
+ TYPE_MAX_VALUE (long_long_integer_type_node));
+ range_cast (r0, short_unsigned_type_node);
+ r1 = irange (TYPE_MIN_VALUE (short_unsigned_type_node),
+ TYPE_MAX_VALUE (short_unsigned_type_node));
+ ASSERT_TRUE (r0 == r1);
+
+ /* The current cast implementation gets a slightly different (also
+ correct) range of [0, 5][20, 30][40, 65535]. Disable for now. */
+#if 0
+ // Test that casting a range with MAX_PAIRS that changes sign is
+ // done conservatively.
+ //
+ // (unsigned short)[-5,5][20,30][40,50]...
+ // => (unsigned short)[-5,50]
+ // => [0,50][65531,65535]
+ r0 = irange (INT16 (-5), INT16 (5));
+ gcc_assert (irange::m_max_pairs * 2 * 10 + 10 < 32767);
+ unsigned i;
+ for (i = 2; i < irange::m_max_pairs * 2; i += 2)
+ {
+ r1 = irange (INT16 (i * 10), INT16 (i * 10 + 10));
+ r0.union_ (r1);
+ }
+ range_cast (r0, short_unsigned_type_node);
+ r1 = irange (UINT16 (0), UINT16 ((i - 2) * 10 + 10));
+ r2 = irange (UINT16 (65531), UINT16 (65535));
+ r1.union_ (r2);
+ ASSERT_TRUE (r0 == r1);
+#endif
+
+ // NOT([10,20]) ==> [-MIN,9][21,MAX].
+ r0 = r1 = irange (INT (10), INT (20));
+ r2 = irange (minint, INT(9));
+ r2.union_ (irange (INT(21), maxint));
+ ASSERT_FALSE (r2.undefined_p ());
+ r1.invert ();
+ ASSERT_TRUE (r1 == r2);
+ // Test that NOT(NOT(x)) == x.
+ r2.invert ();
+ ASSERT_TRUE (r0 == r2);
+
+ // NOT(-MIN,+MAX) is the empty set and should return false.
+ r0 = irange (minint, maxint);
+ r0.invert ();
+ ASSERT_TRUE (r0.undefined_p ());
+ r1.set_undefined ();
+ ASSERT_TRUE (r0 == r1);
+
+ // Test that booleans and their inverse work as expected.
+ r0 = range_zero (boolean_type_node);
+ ASSERT_TRUE (r0 == irange (build_zero_cst (boolean_type_node),
+ build_zero_cst (boolean_type_node)));
+ r0.invert ();
+ ASSERT_TRUE (r0 == irange (build_one_cst (boolean_type_node),
+ build_one_cst (boolean_type_node)));
+
+ // Casting NONZERO to a narrower type will wrap/overflow so
+ // it's just the entire range for the narrower type.
+ //
+ // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
+ // is outside of the range of a smaller range, return the full
+ // smaller range.
+ r0 = range_nonzero (integer_type_node);
+ range_cast (r0, short_integer_type_node);
+ r1 = irange (TYPE_MIN_VALUE (short_integer_type_node),
+ TYPE_MAX_VALUE (short_integer_type_node));
+ ASSERT_TRUE (r0 == r1);
+
+ // Casting NONZERO from a narrower signed to a wider signed.
+ //
+ // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
+ // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
+ r0 = range_nonzero (short_integer_type_node);
+ range_cast (r0, integer_type_node);
+ r1 = irange (INT (-32768), INT (-1));
+ r2 = irange (INT (1), INT (32767));
+ r1.union_ (r2);
+ ASSERT_TRUE (r0 == r1);
+
+ if (irange::m_max_pairs > 2)
+ {
+ // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
+ r0 = irange (INT (10), INT (20));
+ r1 = irange (INT (5), INT (8));
+ r0.union_ (r1);
+ r1 = irange (INT (1), INT (3));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == RANGE3 (1, 3, 5, 8, 10, 20));
+
+ // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
+ r1 = irange (INT (-5), INT (0));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == RANGE3 (-5, 3, 5, 8, 10, 20));
+ }
+
+ // [10,20] U [30,40] ==> [10,20][30,40].
+ r0 = irange (INT (10), INT (20));
+ r1 = irange (INT (30), INT (40));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)),
+ irange (INT (30), INT (40))));
+ if (irange::m_max_pairs > 2)
+ {
+ // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
+ r1 = irange (INT (50), INT (60));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 60));
+ // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
+ r1 = irange (INT (70), INT (80));
+ r0.union_ (r1);
+
+ r2 = RANGE3 (10, 20, 30, 40, 50, 60);
+ r2.union_ (irange (INT (70), INT (80)));
+ ASSERT_TRUE (r0 == r2);
+ }
+
+ // Make sure NULL and non-NULL of pointer types work, and that
+ // inverses of them are consistent.
+ tree voidp = build_pointer_type (void_type_node);
+ r0 = range_zero (voidp);
+ r1 = r0;
+ r0.invert ();
+ r0.invert ();
+ ASSERT_TRUE (r0 == r1);
+
+ if (irange::m_max_pairs > 2)
+ {
+ // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
+ r0 = RANGE3 (10, 20, 30, 40, 50, 60);
+ r1 = irange (INT (6), INT (35));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == range_union (irange (INT (6), INT (40)),
+ irange (INT (50), INT (60))));
+
+ // [10,20][30,40][50,60] U [6,60] => [6,60] */
+ r0 = RANGE3 (10, 20, 30, 40, 50, 60);
+ r1 = irange (INT (6), INT (60));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == irange (INT (6), INT (60)));
+
+ // [10,20][30,40][50,60] U [6,70] => [6,70].
+ r0 = RANGE3 (10, 20, 30, 40, 50, 60);
+ r1 = irange (INT (6), INT (70));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == irange (INT (6), INT (70)));
+
+ // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
+ r0 = RANGE3 (10, 20, 30, 40, 50, 60);
+ r1 = irange (INT (35), INT (70));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)),
+ irange (INT (30), INT (70))));
+ }
+
+ // [10,20][30,40] U [25,70] => [10,70].
+ r0 = range_union (irange (INT (10), INT (20)),
+ irange (INT (30), INT (40)));
+ r1 = irange (INT (25), INT (70));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)),
+ irange (INT (25), INT (70))));
+
+ if (irange::m_max_pairs > 2)
+ {
+ // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
+ r0 = RANGE3 (10, 20, 30, 40, 50, 60);
+ r1 = irange (INT (15), INT (35));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (40)),
+ irange (INT (50), INT (60))));
+ }
+
+ // [10,20] U [15, 30] => [10, 30].
+ r0 = irange (INT (10), INT (20));
+ r1 = irange (INT (15), INT (30));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == irange (INT (10), INT (30)));
+
+ // [10,20] U [25,25] => [10,20][25,25].
+ r0 = irange (INT (10), INT (20));
+ r1 = irange (INT (25), INT (25));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)),
+ irange (INT (25), INT (25))));
+
+ if (irange::m_max_pairs > 2)
+ {
+ // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
+ r0 = RANGE3 (10, 20, 30, 40, 50, 60);
+ r1 = irange (INT (35), INT (35));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 60));
+ }
+
+ // [15,40] U [] => [15,40].
+ r0 = irange (INT (15), INT (40));
+ r1.set_undefined ();
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == irange (INT (15), INT (40)));
+
+ // [10,20] U [10,10] => [10,20].
+ r0 = irange (INT (10), INT (20));
+ r1 = irange (INT (10), INT (10));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == irange (INT (10), INT (20)));
+
+ // [10,20] U [9,9] => [9,20].
+ r0 = irange (INT (10), INT (20));
+ r1 = irange (INT (9), INT (9));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == irange (INT (9), INT (20)));
+
+ if (irange::m_max_pairs > 2)
+ {
+ // [10,10][12,12][20,100] ^ [15,200].
+ r0 = RANGE3 (10, 10, 12, 12, 20, 100);
+ r1 = irange (INT (15), INT (200));
+ r0.intersect (r1);
+ ASSERT_TRUE (r0 == irange (INT (20), INT (100)));
+
+ // [10,20][30,40][50,60] ^ [15,25][38,51][55,70]
+ // => [15,20][38,40][50,51][55,60]
+ r0 = RANGE3 (10, 20, 30, 40, 50, 60);
+ r1 = RANGE3 (15, 25, 38, 51, 55, 70);
+ r0.intersect (r1);
+ if (irange::m_max_pairs == 3)
+ {
+ // When pairs==3, we don't have enough space, so
+ // conservatively handle things. Thus, the ...[50,60].
+ ASSERT_TRUE (r0 == RANGE3 (15, 20, 38, 40, 50, 60));
+ }
+ else
+ {
+ r2 = RANGE3 (15, 20, 38, 40, 50, 51);
+ r2.union_ (irange (INT (55), INT (60)));
+ ASSERT_TRUE (r0 == r2);
+ }
+
+ // [15,20][30,40][50,60] ^ [15,35][40,90][100,200]
+ // => [15,20][30,35][40,60]
+ r0 = RANGE3 (15, 20, 30, 40, 50, 60);
+ r1 = RANGE3 (15, 35, 40, 90, 100, 200);
+ r0.intersect (r1);
+ if (irange::m_max_pairs == 3)
+ {
+ // When pairs==3, we don't have enough space, so
+ // conservatively handle things.
+ ASSERT_TRUE (r0 == RANGE3 (15, 20, 30, 35, 40, 60));
+ }
+ else
+ {
+ r2 = RANGE3 (15, 20, 30, 35, 40, 40);
+ r2.union_ (irange (INT (50), INT (60)));
+ ASSERT_TRUE (r0 == r2);
+ }
+
+ // Test cases where a union inserts a sub-range inside a larger
+ // range.
+ //
+ // [8,10][135,255] U [14,14] => [8,10][14,14][135,255]
+ r0 = range_union (irange (INT (8), INT (10)),
+ irange (INT (135), INT (255)));
+ r1 = irange (INT (14), INT (14));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == RANGE3 (8, 10, 14, 14, 135, 255));
+ }
+
+ // [10,20] ^ [15,30] => [15,20].
+ r0 = irange (INT (10), INT (20));
+ r1 = irange (INT (15), INT (30));
+ r0.intersect (r1);
+ ASSERT_TRUE (r0 == irange (INT (15), INT (20)));
+
+ // [10,20][30,40] ^ [40,50] => [40,40].
+ r0 = range_union (irange (INT (10), INT (20)),
+ irange (INT (30), INT (40)));
+ r1 = irange (INT (40), INT (50));
+ r0.intersect (r1);
+ ASSERT_TRUE (r0 == irange (INT (40), INT (40)));
+
+ // Test non-destructive intersection.
+ r0 = rold = irange (INT (10), INT (20));
+ ASSERT_FALSE (range_intersect (r0, irange (INT (15),
+ INT (30))).undefined_p ());
+ ASSERT_TRUE (r0 == rold);
+
+ // Test the internal sanity of wide_int's wrt HWIs.
+ ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node),
+ TYPE_SIGN (boolean_type_node))
+ == wi::uhwi (1, TYPE_PRECISION (boolean_type_node)));
+
+ // Test irange_storage.
+ r0 = irange (INT (5), INT (10));
+ irange_storage *stow = irange_storage::alloc (r0, integer_type_node);
+ r1 = irange (integer_type_node, stow);
+ ASSERT_TRUE (r0 == r1);
+
+ // Test irange_storage with signed 1-bit fields.
+ tree s1bit_type = make_signed_type (1);
+ r0 = irange (build_int_cst (s1bit_type, -1), build_int_cst (s1bit_type, 0));
+ stow = irange_storage::alloc (r0, s1bit_type);
+ r1 = irange (s1bit_type, stow);
+ ASSERT_TRUE (r0 == r1);
+
+ // Test zero_p().
+ r0 = irange (INT (0), INT (0));
+ ASSERT_TRUE (r0.zero_p ());
+
+ // Test nonzero_p().
+ r0 = irange (INT (0), INT (0));
+ r0.invert ();
+ ASSERT_TRUE (r0.nonzero_p ());
+
+ // Test irange / value_range conversion functions.
+ r0 = irange (VR_ANTI_RANGE, INT (10), INT (20));
+ value_range_base vr = r0;
+ ASSERT_TRUE (vr.kind () == VR_ANTI_RANGE);
+ ASSERT_TRUE (wi::eq_p (10, wi::to_wide (vr.min ()))
+ && wi::eq_p (20, wi::to_wide (vr.max ())));
+ r1 = vr;
+ ASSERT_TRUE (r0 == r1);
+}
+#endif // CHECKING_P
diff --git a/gcc/range.cc b/gcc/range.cc
index 0e13a41..c07154d 100644
--- a/gcc/range.cc
+++ b/gcc/range.cc
@@ -28,7 +28,6 @@ along with GCC; see the file COPYING3. If not see
#include "fold-const.h"
#include "ssa.h"
#include "range.h"
-#include "selftest.h"
#include "wide-int-range.h"
// Common code between the alternate irange implementations.
@@ -133,523 +132,6 @@ range_negatives (tree type)
return r;
}
-#if CHECKING_P
-#include "stor-layout.h"
-
-// Ideally this should go in namespace selftest, but range_tests
-// needs to be a friend of class irange so it can access
-// irange::m_max_pairs.
-
-#define INT(N) build_int_cst (integer_type_node, (N))
-#define UINT(N) build_int_cstu (unsigned_type_node, (N))
-#define INT16(N) build_int_cst (short_integer_type_node, (N))
-#define UINT16(N) build_int_cstu (short_unsigned_type_node, (N))
-#define INT64(N) build_int_cstu (long_long_integer_type_node, (N))
-#define UINT64(N) build_int_cstu (long_long_unsigned_type_node, (N))
-#define UINT128(N) build_int_cstu (u128_type, (N))
-#define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
-#define SCHAR(N) build_int_cst (signed_char_type_node, (N))
-
-#define RANGE3(A,B,C,D,E,F) \
-( i1 = irange (INT (A), INT (B)), \
- i2 = irange (INT (C), INT (D)), \
- i3 = irange (INT (E), INT (F)), \
- i1.union_ (i2), \
- i1.union_ (i3), \
- i1 )
-
-/* Ughhh, this is for range_cast. We should pull out all the
- range_cast tests below into range-op.cc. */
-#include "range-op.h"
-
-// Run all of the selftests within this file.
-
-void
-range_tests ()
-{
- tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
- irange i1, i2, i3;
- irange r0, r1, rold;
-
- // Test that NOT(255) is [0..254] in 8-bit land.
- irange not_255 (VR_ANTI_RANGE, UCHAR (255), UCHAR (255));
- ASSERT_TRUE (not_255 == irange (UCHAR (0), UCHAR (254)));
-
- // Test that NOT(0) is [1..255] in 8-bit land.
- irange not_zero = range_nonzero (unsigned_char_type_node);
- ASSERT_TRUE (not_zero == irange (UCHAR (1), UCHAR (255)));
-
- // Check that [0,127][0x..ffffff80,0x..ffffff]
- // => ~[128, 0x..ffffff7f].
- r0 = irange (UINT128 (0), UINT128 (127));
- tree high = build_minus_one_cst (u128_type);
- // low = -1 - 127 => 0x..ffffff80.
- tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127));
- r1 = irange (low, high); // [0x..ffffff80, 0x..ffffffff]
- // r0 = [0,127][0x..ffffff80,0x..fffffff].
- r0.union_ (r1);
- // r1 = [128, 0x..ffffff7f].
- r1 = irange (UINT128(128),
- fold_build2 (MINUS_EXPR, u128_type,
- build_minus_one_cst (u128_type),
- UINT128(128)));
- r0.invert ();
- ASSERT_TRUE (r0 == r1);
-
- r0.set_varying (integer_type_node);
- tree minint = wide_int_to_tree (integer_type_node, r0.lower_bound ());
- tree maxint = wide_int_to_tree (integer_type_node, r0.upper_bound ());
-
- r0.set_varying (short_integer_type_node);
- tree minshort = wide_int_to_tree (short_integer_type_node, r0.lower_bound ());
- tree maxshort = wide_int_to_tree (short_integer_type_node, r0.upper_bound ());
-
- r0.set_varying (unsigned_type_node);
- tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ());
-
- // Check that ~[0,5] => [6,MAX] for unsigned int.
- r0 = irange (UINT (0), UINT (5));
- r0.invert ();
- ASSERT_TRUE (r0 == irange (UINT(6), maxuint));
-
- // Check that ~[10,MAX] => [0,9] for unsigned int.
- r0 = irange (VR_RANGE, UINT(10), maxuint);
- r0.invert ();
- ASSERT_TRUE (r0 == irange (UINT (0), UINT (9)));
-
- // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
- r0 = irange (VR_ANTI_RANGE, UINT128 (0), UINT128 (5));
- r1 = irange (UINT128(6), build_minus_one_cst (u128_type));
- ASSERT_TRUE (r0 == r1);
-
- // Check that [~5] is really [-MIN,4][6,MAX].
- r0 = irange (VR_ANTI_RANGE, INT (5), INT (5));
- r1 = irange (minint, INT (4));
- r1.union_ (irange (INT (6), maxint));
- ASSERT_FALSE (r1.undefined_p ());
- ASSERT_TRUE (r0 == r1);
-
- r1 = irange (INT (5), INT (5));
- r1.check ();
- irange r2 (r1);
- ASSERT_TRUE (r1 == r2);
-
- r1 = irange (INT (5), INT (10));
- r1.check ();
-
- r1 = irange (integer_type_node,
- wi::to_wide (INT (5)), wi::to_wide (INT (10)));
- r1.check ();
- ASSERT_TRUE (r1.contains_p (INT (7)));
-
- r1 = irange (SCHAR (0), SCHAR (20));
- ASSERT_TRUE (r1.contains_p (SCHAR(15)));
- ASSERT_FALSE (r1.contains_p (SCHAR(300)));
-
- // If a range is in any way outside of the range for the converted
- // to range, default to the range for the new type.
- r1 = irange (integer_zero_node, maxint);
- range_cast (r1, short_integer_type_node);
- ASSERT_TRUE (r1.lower_bound () == wi::to_wide (minshort)
- && r1.upper_bound() == wi::to_wide (maxshort));
-
- // (unsigned char)[-5,-1] => [251,255].
- r0 = rold = irange (SCHAR (-5), SCHAR (-1));
- range_cast (r0, unsigned_char_type_node);
- ASSERT_TRUE (r0 == irange (UCHAR (251), UCHAR (255)));
- range_cast (r0, signed_char_type_node);
- ASSERT_TRUE (r0 == rold);
-
- // (signed char)[15, 150] => [-128,-106][15,127].
- r0 = rold = irange (UCHAR (15), UCHAR (150));
- range_cast (r0, signed_char_type_node);
- r1 = irange (SCHAR (15), SCHAR (127));
- r2 = irange (SCHAR (-128), SCHAR (-106));
- r1.union_ (r2);
- ASSERT_TRUE (r1 == r0);
- range_cast (r0, unsigned_char_type_node);
- ASSERT_TRUE (r0 == rold);
-
- // (unsigned char)[-5, 5] => [0,5][251,255].
- r0 = rold = irange (SCHAR (-5), SCHAR (5));
- range_cast (r0, unsigned_char_type_node);
- r1 = irange (UCHAR (251), UCHAR (255));
- r2 = irange (UCHAR (0), UCHAR (5));
- r1.union_ (r2);
- ASSERT_TRUE (r0 == r1);
- range_cast (r0, signed_char_type_node);
- ASSERT_TRUE (r0 == rold);
-
- // (unsigned char)[-5,5] => [0,5][251,255].
- r0 = irange (INT (-5), INT (5));
- range_cast (r0, unsigned_char_type_node);
- r1 = irange (UCHAR (0), UCHAR (5));
- r1.union_ (irange (UCHAR (251), UCHAR (255)));
- ASSERT_TRUE (r0 == r1);
-
- // (unsigned char)[5U,1974U] => [0,255].
- r0 = irange (UINT (5), UINT (1974));
- range_cast (r0, unsigned_char_type_node);
- ASSERT_TRUE (r0 == irange (UCHAR (0), UCHAR (255)));
- range_cast (r0, integer_type_node);
- // Going to a wider range should not sign extend.
- ASSERT_TRUE (r0 == irange (INT (0), INT (255)));
-
- // (unsigned char)[-350,15] => [0,255].
- r0 = irange (INT (-350), INT (15));
- range_cast (r0, unsigned_char_type_node);
- ASSERT_TRUE (r0 == irange (TYPE_MIN_VALUE (unsigned_char_type_node),
- TYPE_MAX_VALUE (unsigned_char_type_node)));
-
- // Casting [-120,20] from signed char to unsigned short.
- // => [0, 20][0xff88, 0xffff].
- r0 = irange (SCHAR (-120), SCHAR (20));
- range_cast (r0, short_unsigned_type_node);
- r1 = irange (UINT16 (0), UINT16 (20));
- r2 = irange (UINT16 (0xff88), UINT16 (0xffff));
- r1.union_ (r2);
- ASSERT_TRUE (r0 == r1);
- // A truncating cast back to signed char will work because [-120, 20]
- // is representable in signed char.
- range_cast (r0, signed_char_type_node);
- ASSERT_TRUE (r0 == irange (SCHAR (-120), SCHAR (20)));
-
- // unsigned char -> signed short
- // (signed short)[(unsigned char)25, (unsigned char)250]
- // => [(signed short)25, (signed short)250]
- r0 = rold = irange (UCHAR (25), UCHAR (250));
- range_cast (r0, short_integer_type_node);
- r1 = irange (INT16 (25), INT16 (250));
- ASSERT_TRUE (r0 == r1);
- range_cast (r0, unsigned_char_type_node);
- ASSERT_TRUE (r0 == rold);
-
- // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned.
- r0 = irange (TYPE_MIN_VALUE (long_long_integer_type_node),
- TYPE_MAX_VALUE (long_long_integer_type_node));
- range_cast (r0, short_unsigned_type_node);
- r1 = irange (TYPE_MIN_VALUE (short_unsigned_type_node),
- TYPE_MAX_VALUE (short_unsigned_type_node));
- ASSERT_TRUE (r0 == r1);
-
- /* The current cast implementation gets a slightly different (also
- correct) range of [0, 5][20, 30][40, 65535]. Disable for now. */
-#if 0
- // Test that casting a range with MAX_PAIRS that changes sign is
- // done conservatively.
- //
- // (unsigned short)[-5,5][20,30][40,50]...
- // => (unsigned short)[-5,50]
- // => [0,50][65531,65535]
- r0 = irange (INT16 (-5), INT16 (5));
- gcc_assert (irange::m_max_pairs * 2 * 10 + 10 < 32767);
- unsigned i;
- for (i = 2; i < irange::m_max_pairs * 2; i += 2)
- {
- r1 = irange (INT16 (i * 10), INT16 (i * 10 + 10));
- r0.union_ (r1);
- }
- range_cast (r0, short_unsigned_type_node);
- r1 = irange (UINT16 (0), UINT16 ((i - 2) * 10 + 10));
- r2 = irange (UINT16 (65531), UINT16 (65535));
- r1.union_ (r2);
- ASSERT_TRUE (r0 == r1);
-#endif
-
- // NOT([10,20]) ==> [-MIN,9][21,MAX].
- r0 = r1 = irange (INT (10), INT (20));
- r2 = irange (minint, INT(9));
- r2.union_ (irange (INT(21), maxint));
- ASSERT_FALSE (r2.undefined_p ());
- r1.invert ();
- ASSERT_TRUE (r1 == r2);
- // Test that NOT(NOT(x)) == x.
- r2.invert ();
- ASSERT_TRUE (r0 == r2);
-
- // NOT(-MIN,+MAX) is the empty set and should return false.
- r0 = irange (minint, maxint);
- r0.invert ();
- ASSERT_TRUE (r0.undefined_p ());
- r1.set_undefined ();
- ASSERT_TRUE (r0 == r1);
-
- // Test that booleans and their inverse work as expected.
- r0 = range_zero (boolean_type_node);
- ASSERT_TRUE (r0 == irange (build_zero_cst (boolean_type_node),
- build_zero_cst (boolean_type_node)));
- r0.invert ();
- ASSERT_TRUE (r0 == irange (build_one_cst (boolean_type_node),
- build_one_cst (boolean_type_node)));
-
- // Casting NONZERO to a narrower type will wrap/overflow so
- // it's just the entire range for the narrower type.
- //
- // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
- // is outside of the range of a smaller range, return the full
- // smaller range.
- r0 = range_nonzero (integer_type_node);
- range_cast (r0, short_integer_type_node);
- r1 = irange (TYPE_MIN_VALUE (short_integer_type_node),
- TYPE_MAX_VALUE (short_integer_type_node));
- ASSERT_TRUE (r0 == r1);
-
- // Casting NONZERO from a narrower signed to a wider signed.
- //
- // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
- // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
- r0 = range_nonzero (short_integer_type_node);
- range_cast (r0, integer_type_node);
- r1 = irange (INT (-32768), INT (-1));
- r2 = irange (INT (1), INT (32767));
- r1.union_ (r2);
- ASSERT_TRUE (r0 == r1);
-
- if (irange::m_max_pairs > 2)
- {
- // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
- r0 = irange (INT (10), INT (20));
- r1 = irange (INT (5), INT (8));
- r0.union_ (r1);
- r1 = irange (INT (1), INT (3));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == RANGE3 (1, 3, 5, 8, 10, 20));
-
- // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
- r1 = irange (INT (-5), INT (0));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == RANGE3 (-5, 3, 5, 8, 10, 20));
- }
-
- // [10,20] U [30,40] ==> [10,20][30,40].
- r0 = irange (INT (10), INT (20));
- r1 = irange (INT (30), INT (40));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)),
- irange (INT (30), INT (40))));
- if (irange::m_max_pairs > 2)
- {
- // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
- r1 = irange (INT (50), INT (60));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 60));
- // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
- r1 = irange (INT (70), INT (80));
- r0.union_ (r1);
-
- r2 = RANGE3 (10, 20, 30, 40, 50, 60);
- r2.union_ (irange (INT (70), INT (80)));
- ASSERT_TRUE (r0 == r2);
- }
-
- // Make sure NULL and non-NULL of pointer types work, and that
- // inverses of them are consistent.
- tree voidp = build_pointer_type (void_type_node);
- r0 = range_zero (voidp);
- r1 = r0;
- r0.invert ();
- r0.invert ();
- ASSERT_TRUE (r0 == r1);
-
- if (irange::m_max_pairs > 2)
- {
- // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
- r0 = RANGE3 (10, 20, 30, 40, 50, 60);
- r1 = irange (INT (6), INT (35));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == range_union (irange (INT (6), INT (40)),
- irange (INT (50), INT (60))));
-
- // [10,20][30,40][50,60] U [6,60] => [6,60] */
- r0 = RANGE3 (10, 20, 30, 40, 50, 60);
- r1 = irange (INT (6), INT (60));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == irange (INT (6), INT (60)));
-
- // [10,20][30,40][50,60] U [6,70] => [6,70].
- r0 = RANGE3 (10, 20, 30, 40, 50, 60);
- r1 = irange (INT (6), INT (70));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == irange (INT (6), INT (70)));
-
- // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
- r0 = RANGE3 (10, 20, 30, 40, 50, 60);
- r1 = irange (INT (35), INT (70));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)),
- irange (INT (30), INT (70))));
- }
-
- // [10,20][30,40] U [25,70] => [10,70].
- r0 = range_union (irange (INT (10), INT (20)),
- irange (INT (30), INT (40)));
- r1 = irange (INT (25), INT (70));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)),
- irange (INT (25), INT (70))));
-
- if (irange::m_max_pairs > 2)
- {
- // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
- r0 = RANGE3 (10, 20, 30, 40, 50, 60);
- r1 = irange (INT (15), INT (35));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (40)),
- irange (INT (50), INT (60))));
- }
-
- // [10,20] U [15, 30] => [10, 30].
- r0 = irange (INT (10), INT (20));
- r1 = irange (INT (15), INT (30));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == irange (INT (10), INT (30)));
-
- // [10,20] U [25,25] => [10,20][25,25].
- r0 = irange (INT (10), INT (20));
- r1 = irange (INT (25), INT (25));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)),
- irange (INT (25), INT (25))));
-
- if (irange::m_max_pairs > 2)
- {
- // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
- r0 = RANGE3 (10, 20, 30, 40, 50, 60);
- r1 = irange (INT (35), INT (35));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 60));
- }
-
- // [15,40] U [] => [15,40].
- r0 = irange (INT (15), INT (40));
- r1.set_undefined ();
- r0.union_ (r1);
- ASSERT_TRUE (r0 == irange (INT (15), INT (40)));
-
- // [10,20] U [10,10] => [10,20].
- r0 = irange (INT (10), INT (20));
- r1 = irange (INT (10), INT (10));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == irange (INT (10), INT (20)));
-
- // [10,20] U [9,9] => [9,20].
- r0 = irange (INT (10), INT (20));
- r1 = irange (INT (9), INT (9));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == irange (INT (9), INT (20)));
-
- if (irange::m_max_pairs > 2)
- {
- // [10,10][12,12][20,100] ^ [15,200].
- r0 = RANGE3 (10, 10, 12, 12, 20, 100);
- r1 = irange (INT (15), INT (200));
- r0.intersect (r1);
- ASSERT_TRUE (r0 == irange (INT (20), INT (100)));
-
- // [10,20][30,40][50,60] ^ [15,25][38,51][55,70]
- // => [15,20][38,40][50,51][55,60]
- r0 = RANGE3 (10, 20, 30, 40, 50, 60);
- r1 = RANGE3 (15, 25, 38, 51, 55, 70);
- r0.intersect (r1);
- if (irange::m_max_pairs == 3)
- {
- // When pairs==3, we don't have enough space, so
- // conservatively handle things. Thus, the ...[50,60].
- ASSERT_TRUE (r0 == RANGE3 (15, 20, 38, 40, 50, 60));
- }
- else
- {
- r2 = RANGE3 (15, 20, 38, 40, 50, 51);
- r2.union_ (irange (INT (55), INT (60)));
- ASSERT_TRUE (r0 == r2);
- }
-
- // [15,20][30,40][50,60] ^ [15,35][40,90][100,200]
- // => [15,20][30,35][40,60]
- r0 = RANGE3 (15, 20, 30, 40, 50, 60);
- r1 = RANGE3 (15, 35, 40, 90, 100, 200);
- r0.intersect (r1);
- if (irange::m_max_pairs == 3)
- {
- // When pairs==3, we don't have enough space, so
- // conservatively handle things.
- ASSERT_TRUE (r0 == RANGE3 (15, 20, 30, 35, 40, 60));
- }
- else
- {
- r2 = RANGE3 (15, 20, 30, 35, 40, 40);
- r2.union_ (irange (INT (50), INT (60)));
- ASSERT_TRUE (r0 == r2);
- }
-
- // Test cases where a union inserts a sub-range inside a larger
- // range.
- //
- // [8,10][135,255] U [14,14] => [8,10][14,14][135,255]
- r0 = range_union (irange (INT (8), INT (10)),
- irange (INT (135), INT (255)));
- r1 = irange (INT (14), INT (14));
- r0.union_ (r1);
- ASSERT_TRUE (r0 == RANGE3 (8, 10, 14, 14, 135, 255));
- }
-
- // [10,20] ^ [15,30] => [15,20].
- r0 = irange (INT (10), INT (20));
- r1 = irange (INT (15), INT (30));
- r0.intersect (r1);
- ASSERT_TRUE (r0 == irange (INT (15), INT (20)));
-
- // [10,20][30,40] ^ [40,50] => [40,40].
- r0 = range_union (irange (INT (10), INT (20)),
- irange (INT (30), INT (40)));
- r1 = irange (INT (40), INT (50));
- r0.intersect (r1);
- ASSERT_TRUE (r0 == irange (INT (40), INT (40)));
-
- // Test non-destructive intersection.
- r0 = rold = irange (INT (10), INT (20));
- ASSERT_FALSE (range_intersect (r0, irange (INT (15),
- INT (30))).undefined_p ());
- ASSERT_TRUE (r0 == rold);
-
- // Test the internal sanity of wide_int's wrt HWIs.
- ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node),
- TYPE_SIGN (boolean_type_node))
- == wi::uhwi (1, TYPE_PRECISION (boolean_type_node)));
-
- // Test irange_storage.
- r0 = irange (INT (5), INT (10));
- irange_storage *stow = irange_storage::alloc (r0, integer_type_node);
- r1 = irange (integer_type_node, stow);
- ASSERT_TRUE (r0 == r1);
-
- // Test irange_storage with signed 1-bit fields.
- tree s1bit_type = make_signed_type (1);
- r0 = irange (build_int_cst (s1bit_type, -1), build_int_cst (s1bit_type, 0));
- stow = irange_storage::alloc (r0, s1bit_type);
- r1 = irange (s1bit_type, stow);
- ASSERT_TRUE (r0 == r1);
-
- // Test zero_p().
- r0 = irange (INT (0), INT (0));
- ASSERT_TRUE (r0.zero_p ());
-
- // Test nonzero_p().
- r0 = irange (INT (0), INT (0));
- r0.invert ();
- ASSERT_TRUE (r0.nonzero_p ());
-
- // Test irange / value_range conversion functions.
- r0 = irange (VR_ANTI_RANGE, INT (10), INT (20));
- value_range_base vr = r0;
- ASSERT_TRUE (vr.kind () == VR_ANTI_RANGE);
- ASSERT_TRUE (wi::eq_p (10, wi::to_wide (vr.min ()))
- && wi::eq_p (20, wi::to_wide (vr.max ())));
- r1 = vr;
- ASSERT_TRUE (r0 == r1);
-}
-#endif // CHECKING_P
-
#if USE_IRANGE
// Standalone irange implementation.