isl_test2.cc

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  * Copyright 2010      INRIA Saclay
   4  * Copyright 2012-2013 Ecole Normale Superieure
   5  * Copyright 2014      INRIA Rocquencourt
   6  * Copyright 2021-2022 Cerebras Systems
   7  *
   8  * Use of this software is governed by the MIT license
   9  *
  10  * Written by Sven Verdoolaege, K.U.Leuven, Departement
  11  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
  12  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
  13  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
  14  * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
  15  * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
  16  * B.P. 105 - 78153 Le Chesnay, France
  17  * and Cerebras Systems, 1237 E Arques Ave, Sunnyvale, CA, USA
  18  */
  19
  20 #include <assert.h>
  21 #include <stdlib.h>
  22
  23 #include <functional>
  24 #include <ios>
  25 #include <iostream>
  26 #include <sstream>
  27 #include <string>
  28 #include <type_traits>
  29 #include <utility>
  30 #include <vector>
  31
  32 #include <isl/cpp.h>
  33
  34 /* A binary isl function that appears in the C++ bindings
  35  * as a unary method in a class T, taking an extra argument
  36  * of type A1 and returning an object of type R.
  37  */
  38 template <typename A1, typename R, typename T>
  39 using binary_fn = R (T::*)(A1) const;
  40
  41 /* A function for selecting an overload of a pointer to a unary C++ method
  42  * based on the single argument type.
  43  * The object type and the return type are meant to be deduced.
  44  */
  45 template <typename A1, typename R, typename T>
  46 static binary_fn<A1, R, T> const arg(const binary_fn<A1, R, T> &fn)
  47 {
  48         return fn;
  49 }
  50
  51 /* A ternary isl function that appears in the C++ bindings
  52  * as a binary method in a class T, taking extra arguments
  53  * of type A1 and A2 and returning an object of type R.
  54  */
  55 template <typename A1, typename A2, typename R, typename T>
  56 using ternary_fn = R (T::*)(A1, A2) const;
  57
  58 /* A function for selecting an overload of a pointer to a binary C++ method
  59  * based on the (first) argument type(s).
  60  * The object type and the return type are meant to be deduced.
  61  */
  62 template <typename A1, typename A2, typename R, typename T>
  63 static ternary_fn<A1, A2, R, T> const arg(const ternary_fn<A1, A2, R, T> &fn)
  64 {
  65         return fn;
  66 }
  67
  68 /* A description of the input and the output of a unary property.
  69  */
  70 struct unary_prop {
  71         const char *arg;
  72         bool res;
  73 };
  74
  75 /* A description of the input and the output of a unary operation.
  76  */
  77 struct unary {
  78         const char *arg;
  79         const char *res;
  80 };
  81
  82 /* A description of the inputs and the output of a binary operation.
  83  */
  84 struct binary {
  85         const char *arg1;
  86         const char *arg2;
  87         const char *res;
  88 };
  89
  90 /* A description of the inputs and the output of a ternary operation.
  91  */
  92 struct ternary {
  93         const char *arg1;
  94         const char *arg2;
  95         const char *arg3;
  96         const char *res;
  97 };
  98
  99 /* A template function for checking whether two objects
 100  * of the same (isl) type are (obviously) equal.
 101  * The spelling depends on the isl type and
 102  * in particular on whether an equality method is available or
 103  * whether only obvious equality can be tested.
 104  */
 105 template <typename T, typename std::decay<decltype(
 106         std::declval<T>().is_equal(std::declval<T>()))>::type = true>
 107 static bool is_equal(const T &a, const T &b)
 108 {
 109         return a.is_equal(b);
 110 }
 111 template <typename T, typename std::decay<decltype(
 112         std::declval<T>().plain_is_equal(std::declval<T>()))>::type = true>
 113 static bool is_equal(const T &a, const T &b)
 114 {
 115         return a.plain_is_equal(b);
 116 }
 117
 118 /* A helper macro for throwing an isl::exception_invalid with message "msg".
 119  */
 120 #define THROW_INVALID(msg) \
 121         isl::exception::throw_error(isl_error_invalid, msg, __FILE__, __LINE__)
 122
 123 /* Run a sequence of tests of function "fn" with stringification "name" and
 124  * with input and output described by "tests",
 125  * throwing an exception when an unexpected result is produced.
 126  */
 127 template <typename T>
 128 static void test(isl::ctx ctx, bool fn(const T &), const std::string &name,
 129         const std::vector<unary_prop> &tests)
 130 {
 131         for (const auto &test : tests) {
 132                 T obj(ctx, test.arg);
 133                 bool res = fn(obj);
 134                 std::ostringstream ss;
 135
 136                 if (test.res == res)
 137                         continue;
 138
 139                 ss << name << "(" << test.arg << ") = "
 140                    << std::boolalpha << res << "\n"
 141                    << "expecting: "
 142                    << test.res;
 143                 THROW_INVALID(ss.str().c_str());
 144         }
 145 }
 146
 147 /* Run a sequence of tests of method "fn" with stringification "name" and
 148  * with input and output described by "test",
 149  * throwing an exception when an unexpected result is produced.
 150  */
 151 template <typename R, typename T>
 152 static void test(isl::ctx ctx, R (T::*fn)() const, const std::string &name,
 153         const std::vector<unary> &tests)
 154 {
 155         for (const auto &test : tests) {
 156                 T obj(ctx, test.arg);
 157                 R expected(ctx, test.res);
 158                 const auto &res = (obj.*fn)();
 159                 std::ostringstream ss;
 160
 161                 if (is_equal(expected, res))
 162                         continue;
 163
 164                 ss << name << "(" << test.arg << ") =\n"
 165                    << res << "\n"
 166                    << "expecting:\n"
 167                    << expected;
 168                 THROW_INVALID(ss.str().c_str());
 169         }
 170 }
 171
 172 /* Run a sequence of tests of method "fn" with stringification "name" and
 173  * with inputs and output described by "test",
 174  * throwing an exception when an unexpected result is produced.
 175  */
 176 template <typename R, typename T, typename A1>
 177 static void test(isl::ctx ctx, R (T::*fn)(A1) const, const std::string &name,
 178         const std::vector<binary> &tests)
 179 {
 180         for (const auto &test : tests) {
 181                 T obj(ctx, test.arg1);
 182                 A1 arg1(ctx, test.arg2);
 183                 R expected(ctx, test.res);
 184                 const auto &res = (obj.*fn)(arg1);
 185                 std::ostringstream ss;
 186
 187                 if (is_equal(expected, res))
 188                         continue;
 189
 190                 ss << name << "(" << test.arg1 << ", " << test.arg2 << ") =\n"
 191                    << res << "\n"
 192                    << "expecting:\n"
 193                    << expected;
 194                 THROW_INVALID(ss.str().c_str());
 195         }
 196 }
 197
 198 /* Run a sequence of tests of method "fn" with stringification "name" and
 199  * with inputs and output described by "test",
 200  * throwing an exception when an unexpected result is produced.
 201  */
 202 template <typename R, typename T, typename A1, typename A2>
 203 static void test(isl::ctx ctx, R (T::*fn)(A1, A2) const,
 204         const std::string &name, const std::vector<ternary> &tests)
 205 {
 206         for (const auto &test : tests) {
 207                 T obj(ctx, test.arg1);
 208                 A1 arg1(ctx, test.arg2);
 209                 A2 arg2(ctx, test.arg3);
 210                 R expected(ctx, test.res);
 211                 const auto &res = (obj.*fn)(arg1, arg2);
 212                 std::ostringstream ss;
 213
 214                 if (is_equal(expected, res))
 215                         continue;
 216
 217                 ss << name << "(" << test.arg1 << ", " << test.arg2 << ", "
 218                    << test.arg3 << ") =\n"
 219                    << res << "\n"
 220                    << "expecting:\n"
 221                    << expected;
 222                 THROW_INVALID(ss.str().c_str());
 223         }
 224 }
 225
 226 /* A helper macro that calls test with as implicit initial argument "ctx" and
 227  * as extra argument a stringification of "FN".
 228  */
 229 #define C(FN, ...) test(ctx, FN, #FN, __VA_ARGS__)
 230
 231 /* Perform some basic isl::space tests.
 232  */
 233 static void test_space(isl::ctx ctx)
 234 {
 235         C(&isl::space::domain, {
 236         { "{ A[] -> B[] }", "{ A[] }" },
 237         { "{ A[C[] -> D[]] -> B[E[] -> F[]] }", "{ A[C[] -> D[]] }" },
 238         });
 239
 240         C(&isl::space::range, {
 241         { "{ A[] -> B[] }", "{ B[] }" },
 242         { "{ A[C[] -> D[]] -> B[E[] -> F[]] }", "{ B[E[] -> F[]] }" },
 243         });
 244
 245         C(&isl::space::params, {
 246         { "{ A[] -> B[] }", "{ : }" },
 247         { "{ A[C[] -> D[]] -> B[E[] -> F[]] }", "{ : }" },
 248         });
 249 }
 250
 251 /* Is "fn" an expression defined over a single cell?
 252  */
 253 static bool has_single_cell(const isl::pw_multi_aff &fn)
 254 {
 255         const auto &domain = fn.domain();
 256         return fn.gist(domain).isa_multi_aff();
 257 }
 258
 259 /* Does the conversion of "obj" to an isl_pw_multi_aff
 260  * result in an expression defined over a single cell?
 261  */
 262 template <typename T>
 263 static bool has_single_cell_pma(const T &obj)
 264 {
 265         return has_single_cell(obj.as_pw_multi_aff());
 266 }
 267
 268 /* Perform some basic conversion tests.
 269  *
 270  * In particular, check that a map with an output dimension
 271  * that is equal to some integer division over a domain involving
 272  * a local variable without a known integer division expression or
 273  * to some linear combination of integer divisions
 274  * can be converted to a function expressed in the same way.
 275  *
 276  * Also, check that a nested modulo expression can be extracted
 277  * from a set or binary relation representation, or at least
 278  * that a conversion to a function does not result in multiple cells.
 279  */
 280 static void test_conversion(isl::ctx ctx)
 281 {
 282         C(&isl::set::as_pw_multi_aff, {
 283         { "[N=0:] -> { [] }",
 284           "[N=0:] -> { [] }" },
 285         });
 286
 287         C(&isl::multi_pw_aff::as_set, {
 288         { "[n] -> { [] : n >= 0 } ",
 289           "[n] -> { [] : n >= 0 } " },
 290         });
 291
 292         C(&isl::map::as_pw_multi_aff, {
 293         { "{ [a] -> [a//2] : "
 294             "exists (e0: 8*floor((-a + e0)/8) <= -8 - a + 8e0) }",
 295           "{ [a] -> [a//2] : "
 296             "exists (e0: 8*floor((-a + e0)/8) <= -8 - a + 8e0) }" },
 297         { "{ [a, b] -> [(2*floor((a)/8) + floor((b)/6))] }",
 298           "{ [a, b] -> [(2*floor((a)/8) + floor((b)/6))] }" },
 299         });
 300
 301         C(&has_single_cell_pma<isl::set>, {
 302         { "[s=0:23] -> { A[(s//4)%3, s%4, s//12] }", true },
 303         });
 304
 305         C(&has_single_cell_pma<isl::map>, {
 306         { "{ [a] -> [a//2] : "
 307             "exists (e0: 8*floor((-a + e0)/8) <= -8 - a + 8e0) }",
 308           true },
 309         { "{ [s=0:23, t] -> B[((s+1+2t)//4)%3, 2+(s+1+2t)%4, (s+1+2t)//12] }",
 310           true },
 311         { "{ [a=0:31] -> [b=0:3, c] : 4c = 28 - a + b }", true },
 312         });
 313 }
 314
 315 /* Perform some basic preimage tests.
 316  */
 317 static void test_preimage(isl::ctx ctx)
 318 {
 319         C(arg<isl::multi_aff>(&isl::set::preimage), {
 320         { "{ B[i,j] : 0 <= i < 10 and 0 <= j < 100 }",
 321           "{ A[j,i] -> B[i,j] }",
 322           "{ A[j,i] : 0 <= i < 10 and 0 <= j < 100 }" },
 323         { "{ rat: B[i,j] : 0 <= i, j and 3 i + 5 j <= 100 }",
 324           "{ A[a,b] -> B[a/2,b/6] }",
 325           "{ rat: A[a,b] : 0 <= a, b and 9 a + 5 b <= 600 }" },
 326         { "{ B[i,j] : 0 <= i, j and 3 i + 5 j <= 100 }",
 327           "{ A[a,b] -> B[a/2,b/6] }",
 328           "{ A[a,b] : 0 <= a, b and 9 a + 5 b <= 600 and "
 329                     "exists i,j : a = 2 i and b = 6 j }" },
 330         { "[n] -> { S[i] : 0 <= i <= 100 }", "[n] -> { S[n] }",
 331           "[n] -> { : 0 <= n <= 100 }" },
 332         { "{ B[i] : 0 <= i < 100 and exists a : i = 4 a }",
 333           "{ A[a] -> B[2a] }",
 334           "{ A[a] : 0 <= a < 50 and exists b : a = 2 b }" },
 335         { "{ B[i] : 0 <= i < 100 and exists a : i = 4 a }",
 336           "{ A[a] -> B[([a/2])] }",
 337           "{ A[a] : 0 <= a < 200 and exists b : [a/2] = 4 b }" },
 338         { "{ B[i,j,k] : 0 <= i,j,k <= 100 }",
 339           "{ A[a] -> B[a,a,a/3] }",
 340           "{ A[a] : 0 <= a <= 100 and exists b : a = 3 b }" },
 341         { "{ B[i,j] : j = [(i)/2] } ", "{ A[i,j] -> B[i/3,j] }",
 342           "{ A[i,j] : j = [(i)/6] and exists a : i = 3 a }" },
 343         });
 344
 345         C(arg<isl::pw_multi_aff>(&isl::set::preimage), {
 346         { "{ B[i,j] : 0 <= i < 10 and 0 <= j < 100 }",
 347           "{ A[j,i] -> B[i,j] : false }",
 348           "{ A[j,i] : false }" },
 349         });
 350
 351         C(arg<isl::multi_aff>(&isl::union_map::preimage_domain), {
 352         { "{ B[i,j] -> C[2i + 3j] : 0 <= i < 10 and 0 <= j < 100 }",
 353           "{ A[j,i] -> B[i,j] }",
 354           "{ A[j,i] -> C[2i + 3j] : 0 <= i < 10 and 0 <= j < 100 }" },
 355         { "{ B[i] -> C[i]; D[i] -> E[i] }",
 356           "{ A[i] -> B[i + 1] }",
 357           "{ A[i] -> C[i + 1] }" },
 358         { "{ B[i] -> C[i]; B[i] -> E[i] }",
 359           "{ A[i] -> B[i + 1] }",
 360           "{ A[i] -> C[i + 1]; A[i] -> E[i + 1] }" },
 361         { "{ B[i] -> C[([i/2])] }",
 362           "{ A[i] -> B[2i] }",
 363           "{ A[i] -> C[i] }" },
 364         { "{ B[i,j] -> C[([i/2]), ([(i+j)/3])] }",
 365           "{ A[i] -> B[([i/5]), ([i/7])] }",
 366           "{ A[i] -> C[([([i/5])/2]), ([(([i/5])+([i/7]))/3])] }" },
 367         { "[N] -> { B[i] -> C[([N/2]), i, ([N/3])] }",
 368           "[N] -> { A[] -> B[([N/5])] }",
 369           "[N] -> { A[] -> C[([N/2]), ([N/5]), ([N/3])] }" },
 370         { "{ B[i] -> C[i] : exists a : i = 5 a }",
 371           "{ A[i] -> B[2i] }",
 372           "{ A[i] -> C[2i] : exists a : 2i = 5 a }" },
 373         { "{ B[i] -> C[i] : exists a : i = 2 a; "
 374             "B[i] -> D[i] : exists a : i = 2 a + 1 }",
 375           "{ A[i] -> B[2i] }",
 376           "{ A[i] -> C[2i] }" },
 377         { "{ A[i] -> B[i] }", "{ C[i] -> A[(i + floor(i/3))/2] }",
 378           "{ C[i] -> B[j] : 2j = i + floor(i/3) }" },
 379         });
 380
 381         C(arg<isl::multi_aff>(&isl::union_map::preimage_range), {
 382         { "[M] -> { A[a] -> B[a] }", "[M] -> { C[] -> B[floor(M/2)] }",
 383           "[M] -> { A[floor(M/2)] -> C[] }" },
 384         });
 385 }
 386
 387 /* Perform some basic fixed power tests.
 388  */
 389 static void test_fixed_power(isl::ctx ctx)
 390 {
 391         C(arg<isl::val>(&isl::map::fixed_power), {
 392         { "{ [i] -> [i + 1] }", "23",
 393           "{ [i] -> [i + 23] }" },
 394         { "{ [a = 0:1, b = 0:15, c = 0:1, d = 0:1, 0] -> [a, b, c, d, 1]; "
 395             "[a = 0:1, b = 0:15, c = 0:1, 0, 1] -> [a, b, c, 1, 0];  "
 396             "[a = 0:1, b = 0:15, 0, 1, 1] -> [a, b, 1, 0, 0];  "
 397             "[a = 0:1, b = 0:14, 1, 1, 1] -> [a, 1 + b, 0, 0, 0];  "
 398             "[0, 15, 1, 1, 1] -> [1, 0, 0, 0, 0] }",
 399           "128",
 400           "{ [0, b = 0:15, c = 0:1, d = 0:1, e = 0:1] -> [1, b, c, d, e] }" },
 401         });
 402 }
 403
 404 /* Perform some basic intersection tests.
 405  */
 406 static void test_intersect(isl::ctx ctx)
 407 {
 408         C(arg<isl::basic_set>(&isl::basic_map::intersect_params), {
 409         { "[n] -> { A[x] -> B[y] }", "[n] -> { : n >= 0 }",
 410           "[n] -> { A[x] -> B[y] : n >= 0 }" },
 411         });
 412
 413         C(&isl::union_map::intersect_domain_wrapped_domain, {
 414         { "{ [A[x] -> B[y]] -> C[z]; [D[x] -> A[y]] -> E[z] }",
 415           "{ A[0] }",
 416           "{ [A[0] -> B[y]] -> C[z] }" },
 417         { "{ C[z] -> [A[x] -> B[y]]; E[z] -> [D[x] -> A[y]] }",
 418           "{ A[0] }",
 419           "{ }" },
 420         { "{ T[A[x] -> B[y]] -> C[z]; [D[x] -> A[y]] -> E[z] }",
 421           "{ A[0] }",
 422           "{ T[A[0] -> B[y]] -> C[z] }" },
 423         });
 424
 425         C(&isl::union_map::intersect_range_wrapped_domain, {
 426         { "{ [A[x] -> B[y]] -> C[z]; [D[x] -> A[y]] -> E[z] }",
 427           "{ A[0] }",
 428           "{ }" },
 429         { "{ C[z] -> [A[x] -> B[y]]; E[z] -> [D[x] -> A[y]] }",
 430           "{ A[0] }",
 431           "{ C[z] -> [A[0] -> B[y]] }" },
 432         { "{ C[z] -> T[A[x] -> B[y]]; E[z] -> [D[x] -> A[y]] }",
 433           "{ A[0] }",
 434           "{ C[z] -> T[A[0] -> B[y]] }" },
 435         });
 436 }
 437
 438 /* Is the expression for the lexicographic minimum of "obj"
 439  * defined over a single cell?
 440  */
 441 template <typename T>
 442 static bool lexmin_has_single_cell(const T &obj)
 443 {
 444         return has_single_cell(obj.lexmin_pw_multi_aff());
 445 }
 446
 447 /* Perform some basic lexicographic minimization tests.
 448  */
 449 static void test_lexmin(isl::ctx ctx)
 450 {
 451         C(&lexmin_has_single_cell<isl::map>, {
 452         /* The following two inputs represent the same binary relation,
 453          * the second with extra redundant constraints.
 454          * The lexicographic minimum of both should consist of a single cell.
 455          */
 456         { "{ [a=0:11] -> [b] : -1 + b <= 2*floor((a)/6) <= b }", true },
 457         { "{ [a=0:11] -> [b=0:3] : -1 + b <= 2*floor((a)/6) <= b }", true },
 458         });
 459 }
 460
 461 /* Perform some basic gist tests.
 462  */
 463 static void test_gist(isl::ctx ctx)
 464 {
 465         C(arg<isl::set>(&isl::pw_aff::gist), {
 466         { "{ [x] -> [x] : x != 0 }", "{ [x] : x < -1 or x > 1 }",
 467           "{ [x] -> [x] }" },
 468         });
 469
 470         C(&isl::pw_aff::gist_params, {
 471         { "[N] -> { D[x] -> [x] : N >= 0; D[x] -> [0] : N < 0 }",
 472           "[N] -> { : N >= 0 }",
 473           "[N] -> { D[x] -> [x] }" },
 474         });
 475
 476         C(arg<isl::set>(&isl::multi_aff::gist), {
 477         { "{ A[i] -> B[i, i] }", "{ A[0] }",
 478           "{ A[i] -> B[0, 0] }" },
 479         { "[N] -> { A[i] -> B[i, N] }", "[N] -> { A[0] : N = 5 }",
 480           "[N] -> { A[i] -> B[0, 5] }" },
 481         { "[N] -> { B[N + 1, N] }", "[N] -> { : N = 5 }",
 482           "[N] -> { B[6, 5] }" },
 483         { "[N] -> { A[i] -> B[] }", "[N] -> { A[0] : N = 5 }",
 484           "[N] -> { A[i] -> B[] }" },
 485         { "[N] -> { B[] }", "[N] -> { : N = 5 }",
 486           "[N] -> { B[] }" },
 487         });
 488
 489         C(&isl::multi_aff::gist_params, {
 490         { "[N] -> { A[i] -> B[i, N] }", "[N] -> { : N = 5 }",
 491           "[N] -> { A[i] -> B[i, 5] }" },
 492         { "[N] -> { B[N + 1, N] }", "[N] -> { : N = 5 }",
 493           "[N] -> { B[6, 5] }" },
 494         { "[N] -> { A[i] -> B[] }", "[N] -> { : N = 5 }",
 495           "[N] -> { A[i] -> B[] }" },
 496         { "[N] -> { B[] }", "[N] -> { : N = 5 }",
 497           "[N] -> { B[] }" },
 498         });
 499
 500         C(arg<isl::set>(&isl::multi_pw_aff::gist), {
 501         { "{ A[i] -> B[i, i] : i >= 0 }", "{ A[0] }",
 502           "{ A[i] -> B[0, 0] }" },
 503         { "[N] -> { A[i] -> B[i, N] : N >= 0 }", "[N] -> { A[0] : N = 5 }",
 504           "[N] -> { A[i] -> B[0, 5] }" },
 505         { "[N] -> { B[N + 1, N] }", "[N] -> { : N = 5 }",
 506           "[N] -> { B[6, 5] }" },
 507         { "[N] -> { A[i] -> B[] }", "[N] -> { A[0] : N = 5 }",
 508           "[N] -> { A[i] -> B[] }" },
 509         { "[N] -> { B[] }", "[N] -> { : N = 5 }",
 510           "[N] -> { B[] }" },
 511         { "{ A[i=0:10] -> B[i] }", "{ A[5] }",
 512           "{ A[i] -> B[5] }" },
 513         { "{ A[0:10] -> B[] }", "{ A[0:10] }",
 514           "{ A[i] -> B[] }" },
 515         { "[N] -> { A[i] -> B[] : N >= 0 }", "[N] -> { A[0] : N = 5 }",
 516           "[N] -> { A[i] -> B[] }" },
 517         { "[N] -> { B[] : N >= 0 }", "[N] -> { : N = 5 }",
 518           "[N] -> { B[] }" },
 519         { "[N] -> { B[] : N = 5 }", "[N] -> { : N >= 0 }",
 520           "[N] -> { B[] : N = 5 }" },
 521         });
 522
 523         C(&isl::multi_pw_aff::gist_params, {
 524         { "[N] -> { A[i] -> B[i, N] : N >= 0 }", "[N] -> { : N = 5 }",
 525           "[N] -> { A[i] -> B[i, 5] }" },
 526         { "[N] -> { B[N + 1, N] }", "[N] -> { : N = 5 }",
 527           "[N] -> { B[6, 5] }" },
 528         { "[N] -> { A[i] -> B[] : N >= 0 }", "[N] -> { : N = 5 }",
 529           "[N] -> { A[i] -> B[] }" },
 530         { "[N] -> { B[] : N >= 0 }", "[N] -> { : N = 5 }",
 531           "[N] -> { B[] }" },
 532         { "[N] -> { B[] : N >= 5 }", "[N] -> { : N >= 0 }",
 533           "[N] -> { B[] : N >= 5 }" },
 534         });
 535
 536         C(&isl::multi_union_pw_aff::gist, {
 537         { "C[{ B[i,i] -> [3i] }]", "{ B[i,i] }",
 538           "C[{ B[i,j] -> [3i] }]" },
 539         { "(C[] : { B[i,i] })", "{ B[i,i] }",
 540           "(C[] : { B[i,j] })" },
 541         { "[N] -> (C[] : { B[N,N] })", "[N] -> { B[N,N] }",
 542           "[N] -> (C[] : { B[i,j] })" },
 543         { "C[]", "{ B[i,i] }",
 544           "C[]" },
 545         { "[N] -> (C[] : { B[i,i] : N >= 0 })", "{ B[i,i] }",
 546           "[N] -> (C[] : { B[i,j] : N >= 0 })" },
 547         { "[N] -> (C[] : { : N >= 0 })", "{ B[i,i] }",
 548           "[N] -> (C[] : { : N >= 0 })" },
 549         { "[N] -> (C[] : { : N >= 0 })", "[N] -> { B[i,i] : N >= 0 }",
 550           "[N] -> C[]" },
 551         });
 552
 553         C(&isl::multi_union_pw_aff::gist_params, {
 554         { "[N] -> C[{ B[i,i] -> [3i + N] }]", "[N] -> { : N = 1 }",
 555           "[N] -> C[{ B[i,i] -> [3i + 1] }]" },
 556         { "C[{ B[i,i] -> [3i] }]", "[N] -> { : N >= 0 }",
 557           "[N] -> C[{ B[i,i] -> [3i] }]" },
 558         { "[N] -> C[{ B[i,i] -> [3i] : N >= 0 }]", "[N] -> { : N >= 0 }",
 559           "[N] -> C[{ B[i,i] -> [3i] }]" },
 560         { "[N] -> C[{ B[i,i] -> [3i] : N >= 1 }]", "[N] -> { : N >= 0 }",
 561           "[N] -> C[{ B[i,i] -> [3i] : N >= 1 }]" },
 562         { "[N] -> (C[] : { B[i,i] : N >= 0 })", "[N] -> { : N >= 0 }",
 563           "[N] -> (C[] : { B[i,i] })" },
 564         { "[N] -> (C[] : { : N >= 0 })", "[N] -> { : N >= 0 }",
 565           "[N] -> C[]" },
 566         { "C[{ B[i,i] -> [3i] }]", "[N] -> { : N >= 0 }",
 567           "[N] -> C[{ B[i,i] -> [3i] }]" },
 568         });
 569 }
 570
 571 /* Perform tests that project out parameters.
 572  */
 573 static void test_project(isl::ctx ctx)
 574 {
 575         C(arg<isl::id>(&isl::union_map::project_out_param), {
 576         { "[N] -> { D[i] -> A[0:N-1]; D[i] -> B[i] }", "N",
 577           "{ D[i] -> A[0:]; D[i] -> B[i] }" },
 578         { "[N] -> { D[i] -> A[0:N-1]; D[i] -> B[i] }", "M",
 579           "[N] -> { D[i] -> A[0:N-1]; D[i] -> B[i] }" },
 580         });
 581
 582         C(arg<isl::id_list>(&isl::union_map::project_out_param), {
 583         { "[M, N, O] -> { D[i] -> A[j] : i <= j < M, N, O }", "(M, N)",
 584           "[O] -> { D[i] -> A[j] : i <= j < O }" },
 585         });
 586 }
 587
 588 /* Perform some basic reverse tests.
 589  */
 590 static void test_reverse(isl::ctx ctx)
 591 {
 592         C(&isl::aff::domain_reverse, {
 593         { "{ T[A[] -> B[*]] -> [0] }",
 594           "{ [B[*] -> A[]] -> [0] }" },
 595         { "{ T[A[] -> A[]] -> [0] }",
 596           "{ T[A[] -> A[]] -> [0] }" },
 597         { "{ [A[x] -> B[y]] -> [5*(x // 2) + 7*(y // 3)] }",
 598           "{ [B[y] -> A[x]] -> [5*(x // 2) + 7*(y // 3)] }" },
 599         });
 600
 601         C(&isl::multi_aff::domain_reverse, {
 602         { "{ [A[x] -> B[y]] -> [5*(x // 2) + 7*(y // 3)] }",
 603           "{ [B[y] -> A[x]] -> [5*(x // 2) + 7*(y // 3)] }" },
 604         { "{ [A[x] -> B[y]] -> T[5*(x // 2) + 7*(y // 3), 0] }",
 605           "{ [B[y] -> A[x]] -> T[5*(x // 2) + 7*(y // 3), 0] }" },
 606         });
 607
 608         C(&isl::set::wrapped_reverse, {
 609         { "{ T[A[] -> B[*]] }",
 610           "{ [B[*] -> A[]] }" },
 611         { "{ T[A[] -> A[]] }",
 612           "{ T[A[] -> A[]] }" },
 613         { "{ [A[x] -> B[2x]] }",
 614           "{ [B[y] -> A[x]] : y = 2x }" },
 615         });
 616
 617         C(&isl::pw_aff::domain_reverse, {
 618         { "{ [A[x] -> B[y]] -> [5*(x // 2) + 7*(y // 3)] }",
 619           "{ [B[y] -> A[x]] -> [5*(x // 2) + 7*(y // 3)] }" },
 620         { "{ [A[x] -> B[y]] -> [5*(x // 2) + 7*(y // 3)] : x > y }",
 621           "{ [B[y] -> A[x]] -> [5*(x // 2) + 7*(y // 3)] : x > y }" },
 622         { "{ [A[i] -> B[i + 1]] -> [i + 2] }",
 623           "{ [B[i] -> A[i - 1]] -> [i + 1] }" },
 624         });
 625
 626         C(&isl::pw_multi_aff::domain_reverse, {
 627         { "{ [A[x] -> B[y]] -> T[5*(x // 2) + 7*(y // 3), 0] : x > y }",
 628           "{ [B[y] -> A[x]] -> T[5*(x // 2) + 7*(y // 3), 0] : x > y }" },
 629         { "{ [A[i] -> B[i + 1]] -> T[0, i + 2] }",
 630           "{ [B[i] -> A[i - 1]] -> T[0, i + 1] }" },
 631         });
 632
 633         C(&isl::multi_pw_aff::domain_reverse, {
 634         { "{ [A[x] -> B[y]] -> T[5*(x // 2) + 7*(y // 3) : x > y, 0] }",
 635           "{ [B[y] -> A[x]] -> T[5*(x // 2) + 7*(y // 3) : x > y, 0] }" },
 636         });
 637
 638         C(&isl::map::domain_reverse, {
 639         { "{ [A[] -> B[]] -> [C[] -> D[]] }",
 640           "{ [B[] -> A[]] -> [C[] -> D[]] }" },
 641         { "{ N[B[] -> C[]] -> A[] }",
 642           "{ [C[] -> B[]] -> A[] }" },
 643         { "{ N[B[x] -> B[y]] -> A[] }",
 644           "{ N[B[*] -> B[*]] -> A[] }" },
 645         });
 646
 647         C(&isl::union_map::domain_reverse, {
 648         { "{ [A[] -> B[]] -> [C[] -> D[]] }",
 649           "{ [B[] -> A[]] -> [C[] -> D[]] }" },
 650         { "{ A[] -> [B[] -> C[]]; A[] -> B[]; A[0] -> N[B[1] -> B[2]] }",
 651           "{ }" },
 652         { "{ N[B[] -> C[]] -> A[] }",
 653           "{ [C[] -> B[]] -> A[] }" },
 654         { "{ N[B[x] -> B[y]] -> A[] }",
 655           "{ N[B[*] -> B[*]] -> A[] }" },
 656         });
 657
 658         C(&isl::union_map::range_reverse, {
 659         { "{ A[] -> [B[] -> C[]]; A[] -> B[]; A[0] -> N[B[1] -> B[2]] }",
 660           "{ A[] -> [C[] -> B[]]; A[0] -> N[B[2] -> B[1]] }" },
 661         { "{ A[] -> N[B[] -> C[]] }",
 662           "{ A[] -> [C[] -> B[]] }" },
 663         { "{ A[] -> N[B[x] -> B[y]] }",
 664           "{ A[] -> N[B[*] -> B[*]] }" },
 665         });
 666 }
 667
 668 /* Perform some basic scaling tests.
 669  */
 670 static void test_scale(isl::ctx ctx)
 671 {
 672         C(arg<isl::multi_val>(&isl::pw_multi_aff::scale), {
 673         { "{ A[a] -> B[a, a + 1, a - 1] : a >= 0 }", "{ B[2, 7, 0] }",
 674           "{ A[a] -> B[2a, 7a + 7, 0] : a >= 0 }" },
 675         });
 676         C(arg<isl::multi_val>(&isl::pw_multi_aff::scale), {
 677         { "{ A[a] -> B[1, a - 1] : a >= 0 }", "{ B[1/2, 7] }",
 678           "{ A[a] -> B[1/2, 7a - 7] : a >= 0 }" },
 679         });
 680
 681         C(arg<isl::multi_val>(&isl::pw_multi_aff::scale_down), {
 682         { "{ A[a] -> B[a, a + 1] : a >= 0 }", "{ B[2, 7] }",
 683           "{ A[a] -> B[a/2, (a + 1)/7] : a >= 0 }" },
 684         });
 685         C(arg<isl::multi_val>(&isl::pw_multi_aff::scale_down), {
 686         { "{ A[a] -> B[a, a - 1] : a >= 0 }", "{ B[2, 1/7] }",
 687           "{ A[a] -> B[a/2, 7a - 7] : a >= 0 }" },
 688         });
 689 }
 690
 691 /* Perform some basic isl::id_to_id tests.
 692  */
 693 static void test_id_to_id(isl::ctx ctx)
 694 {
 695         C((arg<isl::id, isl::id>(&isl::id_to_id::set)), {
 696         { "{ }", "a", "b",
 697           "{ a: b }" },
 698         { "{ a: b }", "a", "b",
 699           "{ a: b }" },
 700         { "{ a: c }", "a", "b",
 701           "{ a: b }" },
 702         { "{ a: b }", "b", "a",
 703           "{ a: b, b: a }" },
 704         { "{ a: b }", "b", "a",
 705           "{ b: a, a: b }" },
 706         });
 707 }
 708
 709 /* The list of tests to perform.
 710  */
 711 static std::vector<std::pair<const char *, void (*)(isl::ctx)>> tests =
 712 {
 713         { "space", &test_space },
 714         { "conversion", &test_conversion },
 715         { "preimage", &test_preimage },
 716         { "fixed power", &test_fixed_power },
 717         { "intersect", &test_intersect },
 718         { "lexmin", &test_lexmin },
 719         { "gist", &test_gist },
 720         { "project out parameters", &test_project },
 721         { "reverse", &test_reverse },
 722         { "scale", &test_scale },
 723         { "id-to-id", &test_id_to_id },
 724 };
 725
 726 /* Perform some basic checks by means of the C++ bindings.
 727  */
 728 int main(int argc, char **argv)
 729 {
 730         int ret = EXIT_SUCCESS;
 731         struct isl_ctx *ctx;
 732         struct isl_options *options;
 733
 734         options = isl_options_new_with_defaults();
 735         assert(options);
 736         argc = isl_options_parse(options, argc, argv, ISL_ARG_ALL);
 737         ctx = isl_ctx_alloc_with_options(&isl_options_args, options);
 738
 739         try {
 740                 for (const auto &f : tests) {
 741                         std::cout << f.first << "\n";
 742                         f.second(ctx);
 743                 }
 744         } catch (const isl::exception &e) {
 745                 std::cerr << e.what() << "\n";
 746                 ret = EXIT_FAILURE;
 747         }
 748
 749         isl_ctx_free(ctx);
 750         return ret;
 751 }