445 lines · plain
1/*2 * Copyright 2008-2009 Katholieke Universiteit Leuven3 * Copyright 2010 INRIA Saclay4 * Copyright 2012-2013 Ecole Normale Superieure5 * Copyright 2014 INRIA Rocquencourt6 * Copyright 2021-2022 Cerebras Systems7 *8 * Use of this software is governed by the MIT license9 *10 * Written by Sven Verdoolaege, K.U.Leuven, Departement11 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium12 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,13 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France14 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France15 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,16 * B.P. 105 - 78153 Le Chesnay, France17 * and Cerebras Systems, 1237 E Arques Ave, Sunnyvale, CA, USA18 */19 20#include <assert.h>21#include <stdlib.h>22 23#include <functional>24#include <iostream>25#include <sstream>26#include <string>27#include <type_traits>28#include <utility>29#include <vector>30 31#include <isl/cpp.h>32 33/* A binary isl function that appears in the C++ bindings34 * as a unary method in a class T, taking an extra argument35 * of type A1 and returning an object of type R.36 */37template <typename A1, typename R, typename T>38using binary_fn = R (T::*)(A1) const;39 40/* A function for selecting an overload of a pointer to a unary C++ method41 * based on the single argument type.42 * The object type and the return type are meant to be deduced.43 */44template <typename A1, typename R, typename T>45static binary_fn<A1, R, T> const arg(const binary_fn<A1, R, T> &fn)46{47 return fn;48}49 50/* A ternary isl function that appears in the C++ bindings51 * as a binary method in a class T, taking extra arguments52 * of type A1 and A2 and returning an object of type R.53 */54template <typename A1, typename A2, typename R, typename T>55using ternary_fn = R (T::*)(A1, A2) const;56 57/* A function for selecting an overload of a pointer to a binary C++ method58 * based on the (first) argument type(s).59 * The object type and the return type are meant to be deduced.60 */61template <typename A1, typename A2, typename R, typename T>62static ternary_fn<A1, A2, R, T> const arg(const ternary_fn<A1, A2, R, T> &fn)63{64 return fn;65}66 67/* A description of the input and the output of a unary operation.68 */69struct unary {70 const char *arg;71 const char *res;72};73 74/* A description of the inputs and the output of a binary operation.75 */76struct binary {77 const char *arg1;78 const char *arg2;79 const char *res;80};81 82/* A description of the inputs and the output of a ternary operation.83 */84struct ternary {85 const char *arg1;86 const char *arg2;87 const char *arg3;88 const char *res;89};90 91/* A template function for checking whether two objects92 * of the same (isl) type are (obviously) equal.93 * The spelling depends on the isl type and94 * in particular on whether an equality method is available or95 * whether only obvious equality can be tested.96 */97template <typename T, typename std::decay<decltype(98 std::declval<T>().is_equal(std::declval<T>()))>::type = true>99static bool is_equal(const T &a, const T &b)100{101 return a.is_equal(b);102}103template <typename T, typename std::decay<decltype(104 std::declval<T>().plain_is_equal(std::declval<T>()))>::type = true>105static bool is_equal(const T &a, const T &b)106{107 return a.plain_is_equal(b);108}109 110/* A helper macro for throwing an isl::exception_invalid with message "msg".111 */112#define THROW_INVALID(msg) \113 isl::exception::throw_error(isl_error_invalid, msg, __FILE__, __LINE__)114 115/* Run a sequence of tests of method "fn" with stringification "name" and116 * with input and output described by "test",117 * throwing an exception when an unexpected result is produced.118 */119template <typename R, typename T>120static void test(isl::ctx ctx, R (T::*fn)() const, const std::string &name,121 const std::vector<unary> &tests)122{123 for (const auto &test : tests) {124 T obj(ctx, test.arg);125 R expected(ctx, test.res);126 const auto &res = (obj.*fn)();127 std::ostringstream ss;128 129 if (is_equal(expected, res))130 continue;131 132 ss << name << "(" << test.arg << ") =\n"133 << res << "\n"134 << "expecting:\n"135 << expected;136 THROW_INVALID(ss.str().c_str());137 }138}139 140/* Run a sequence of tests of method "fn" with stringification "name" and141 * with inputs and output described by "test",142 * throwing an exception when an unexpected result is produced.143 */144template <typename R, typename T, typename A1>145static void test(isl::ctx ctx, R (T::*fn)(A1) const, const std::string &name,146 const std::vector<binary> &tests)147{148 for (const auto &test : tests) {149 T obj(ctx, test.arg1);150 A1 arg1(ctx, test.arg2);151 R expected(ctx, test.res);152 const auto &res = (obj.*fn)(arg1);153 std::ostringstream ss;154 155 if (is_equal(expected, res))156 continue;157 158 ss << name << "(" << test.arg1 << ", " << test.arg2 << ") =\n"159 << res << "\n"160 << "expecting:\n"161 << test.res;162 THROW_INVALID(ss.str().c_str());163 }164}165 166/* Run a sequence of tests of method "fn" with stringification "name" and167 * with inputs and output described by "test",168 * throwing an exception when an unexpected result is produced.169 */170template <typename R, typename T, typename A1, typename A2>171static void test(isl::ctx ctx, R (T::*fn)(A1, A2) const,172 const std::string &name, const std::vector<ternary> &tests)173{174 for (const auto &test : tests) {175 T obj(ctx, test.arg1);176 A1 arg1(ctx, test.arg2);177 A2 arg2(ctx, test.arg3);178 R expected(ctx, test.res);179 const auto &res = (obj.*fn)(arg1, arg2);180 std::ostringstream ss;181 182 if (is_equal(expected, res))183 continue;184 185 ss << name << "(" << test.arg1 << ", " << test.arg2 << ", "186 << test.arg3 << ") =\n"187 << res << "\n"188 << "expecting:\n"189 << expected;190 THROW_INVALID(ss.str().c_str());191 }192}193 194/* A helper macro that calls test with as implicit initial argument "ctx" and195 * as extra argument a stringification of "FN".196 */197#define C(FN, ...) test(ctx, FN, #FN, __VA_ARGS__)198 199/* Perform some basic isl::space tests.200 */201static void test_space(isl::ctx ctx)202{203 C(&isl::space::domain, {204 { "{ A[] -> B[] }", "{ A[] }" },205 { "{ A[C[] -> D[]] -> B[E[] -> F[]] }", "{ A[C[] -> D[]] }" },206 });207 208 C(&isl::space::range, {209 { "{ A[] -> B[] }", "{ B[] }" },210 { "{ A[C[] -> D[]] -> B[E[] -> F[]] }", "{ B[E[] -> F[]] }" },211 });212 213 C(&isl::space::params, {214 { "{ A[] -> B[] }", "{ : }" },215 { "{ A[C[] -> D[]] -> B[E[] -> F[]] }", "{ : }" },216 });217}218 219/* Perform some basic conversion tests.220 */221static void test_conversion(isl::ctx ctx)222{223 C(&isl::multi_pw_aff::as_set, {224 { "[n] -> { [] : n >= 0 } ",225 "[n] -> { [] : n >= 0 } " },226 });227}228 229/* Perform some basic preimage tests.230 */231static void test_preimage(isl::ctx ctx)232{233 C(arg<isl::multi_aff>(&isl::set::preimage), {234 { "{ B[i,j] : 0 <= i < 10 and 0 <= j < 100 }",235 "{ A[j,i] -> B[i,j] }",236 "{ A[j,i] : 0 <= i < 10 and 0 <= j < 100 }" },237 { "{ rat: B[i,j] : 0 <= i, j and 3 i + 5 j <= 100 }",238 "{ A[a,b] -> B[a/2,b/6] }",239 "{ rat: A[a,b] : 0 <= a, b and 9 a + 5 b <= 600 }" },240 { "{ B[i,j] : 0 <= i, j and 3 i + 5 j <= 100 }",241 "{ A[a,b] -> B[a/2,b/6] }",242 "{ A[a,b] : 0 <= a, b and 9 a + 5 b <= 600 and "243 "exists i,j : a = 2 i and b = 6 j }" },244 { "[n] -> { S[i] : 0 <= i <= 100 }", "[n] -> { S[n] }",245 "[n] -> { : 0 <= n <= 100 }" },246 { "{ B[i] : 0 <= i < 100 and exists a : i = 4 a }",247 "{ A[a] -> B[2a] }",248 "{ A[a] : 0 <= a < 50 and exists b : a = 2 b }" },249 { "{ B[i] : 0 <= i < 100 and exists a : i = 4 a }",250 "{ A[a] -> B[([a/2])] }",251 "{ A[a] : 0 <= a < 200 and exists b : [a/2] = 4 b }" },252 { "{ B[i,j,k] : 0 <= i,j,k <= 100 }",253 "{ A[a] -> B[a,a,a/3] }",254 "{ A[a] : 0 <= a <= 100 and exists b : a = 3 b }" },255 { "{ B[i,j] : j = [(i)/2] } ", "{ A[i,j] -> B[i/3,j] }",256 "{ A[i,j] : j = [(i)/6] and exists a : i = 3 a }" },257 });258 259 C(arg<isl::multi_aff>(&isl::union_map::preimage_domain), {260 { "{ B[i,j] -> C[2i + 3j] : 0 <= i < 10 and 0 <= j < 100 }",261 "{ A[j,i] -> B[i,j] }",262 "{ A[j,i] -> C[2i + 3j] : 0 <= i < 10 and 0 <= j < 100 }" },263 { "{ B[i] -> C[i]; D[i] -> E[i] }",264 "{ A[i] -> B[i + 1] }",265 "{ A[i] -> C[i + 1] }" },266 { "{ B[i] -> C[i]; B[i] -> E[i] }",267 "{ A[i] -> B[i + 1] }",268 "{ A[i] -> C[i + 1]; A[i] -> E[i + 1] }" },269 { "{ B[i] -> C[([i/2])] }",270 "{ A[i] -> B[2i] }",271 "{ A[i] -> C[i] }" },272 { "{ B[i,j] -> C[([i/2]), ([(i+j)/3])] }",273 "{ A[i] -> B[([i/5]), ([i/7])] }",274 "{ A[i] -> C[([([i/5])/2]), ([(([i/5])+([i/7]))/3])] }" },275 { "[N] -> { B[i] -> C[([N/2]), i, ([N/3])] }",276 "[N] -> { A[] -> B[([N/5])] }",277 "[N] -> { A[] -> C[([N/2]), ([N/5]), ([N/3])] }" },278 { "{ B[i] -> C[i] : exists a : i = 5 a }",279 "{ A[i] -> B[2i] }",280 "{ A[i] -> C[2i] : exists a : 2i = 5 a }" },281 { "{ B[i] -> C[i] : exists a : i = 2 a; "282 "B[i] -> D[i] : exists a : i = 2 a + 1 }",283 "{ A[i] -> B[2i] }",284 "{ A[i] -> C[2i] }" },285 { "{ A[i] -> B[i] }", "{ C[i] -> A[(i + floor(i/3))/2] }",286 "{ C[i] -> B[j] : 2j = i + floor(i/3) }" },287 });288 289 C(arg<isl::multi_aff>(&isl::union_map::preimage_range), {290 { "[M] -> { A[a] -> B[a] }", "[M] -> { C[] -> B[floor(M/2)] }",291 "[M] -> { A[floor(M/2)] -> C[] }" },292 });293}294 295/* Perform some basic fixed power tests.296 */297static void test_fixed_power(isl::ctx ctx)298{299 C(arg<isl::val>(&isl::map::fixed_power), {300 { "{ [i] -> [i + 1] }", "23",301 "{ [i] -> [i + 23] }" },302 { "{ [a = 0:1, b = 0:15, c = 0:1, d = 0:1, 0] -> [a, b, c, d, 1]; "303 "[a = 0:1, b = 0:15, c = 0:1, 0, 1] -> [a, b, c, 1, 0]; "304 "[a = 0:1, b = 0:15, 0, 1, 1] -> [a, b, 1, 0, 0]; "305 "[a = 0:1, b = 0:14, 1, 1, 1] -> [a, 1 + b, 0, 0, 0]; "306 "[0, 15, 1, 1, 1] -> [1, 0, 0, 0, 0] }",307 "128",308 "{ [0, b = 0:15, c = 0:1, d = 0:1, e = 0:1] -> [1, b, c, d, e] }" },309 });310}311 312/* Perform some basic intersection tests.313 */314static void test_intersect(isl::ctx ctx)315{316 C(&isl::union_map::intersect_domain_wrapped_domain, {317 { "{ [A[x] -> B[y]] -> C[z]; [D[x] -> A[y]] -> E[z] }",318 "{ A[0] }",319 "{ [A[0] -> B[y]] -> C[z] }" },320 { "{ C[z] -> [A[x] -> B[y]]; E[z] -> [D[x] -> A[y]] }",321 "{ A[0] }",322 "{ }" },323 });324 325 C(&isl::union_map::intersect_range_wrapped_domain, {326 { "{ [A[x] -> B[y]] -> C[z]; [D[x] -> A[y]] -> E[z] }",327 "{ A[0] }",328 "{ }" },329 { "{ C[z] -> [A[x] -> B[y]]; E[z] -> [D[x] -> A[y]] }",330 "{ A[0] }",331 "{ C[z] -> [A[0] -> B[y]] }" },332 });333}334 335/* Perform some basic gist tests.336 */337static void test_gist(isl::ctx ctx)338{339 C(&isl::pw_aff::gist_params, {340 { "[N] -> { D[x] -> [x] : N >= 0; D[x] -> [0] : N < 0 }",341 "[N] -> { : N >= 0 }",342 "[N] -> { D[x] -> [x] }" },343 });344}345 346/* Perform tests that project out parameters.347 */348static void test_project(isl::ctx ctx)349{350 C(arg<isl::id>(&isl::union_map::project_out_param), {351 { "[N] -> { D[i] -> A[0:N-1]; D[i] -> B[i] }", "N",352 "{ D[i] -> A[0:]; D[i] -> B[i] }" },353 { "[N] -> { D[i] -> A[0:N-1]; D[i] -> B[i] }", "M",354 "[N] -> { D[i] -> A[0:N-1]; D[i] -> B[i] }" },355 });356 357 C(arg<isl::id_list>(&isl::union_map::project_out_param), {358 { "[M, N, O] -> { D[i] -> A[j] : i <= j < M, N, O }", "(M, N)",359 "[O] -> { D[i] -> A[j] : i <= j < O }" },360 });361}362 363/* Perform some basic scaling tests.364 */365static void test_scale(isl::ctx ctx)366{367 C(arg<isl::multi_val>(&isl::pw_multi_aff::scale), {368 { "{ A[a] -> B[a, a + 1, a - 1] : a >= 0 }", "{ B[2, 7, 0] }",369 "{ A[a] -> B[2a, 7a + 7, 0] : a >= 0 }" },370 });371 C(arg<isl::multi_val>(&isl::pw_multi_aff::scale), {372 { "{ A[a] -> B[1, a - 1] : a >= 0 }", "{ B[1/2, 7] }",373 "{ A[a] -> B[1/2, 7a - 7] : a >= 0 }" },374 });375 376 C(arg<isl::multi_val>(&isl::pw_multi_aff::scale_down), {377 { "{ A[a] -> B[a, a + 1] : a >= 0 }", "{ B[2, 7] }",378 "{ A[a] -> B[a/2, (a + 1)/7] : a >= 0 }" },379 });380 C(arg<isl::multi_val>(&isl::pw_multi_aff::scale_down), {381 { "{ A[a] -> B[a, a - 1] : a >= 0 }", "{ B[2, 1/7] }",382 "{ A[a] -> B[a/2, 7a - 7] : a >= 0 }" },383 });384}385 386/* Perform some basic isl::id_to_id tests.387 */388static void test_id_to_id(isl::ctx ctx)389{390 C((arg<isl::id, isl::id>(&isl::id_to_id::set)), {391 { "{ }", "a", "b",392 "{ a: b }" },393 { "{ a: b }", "a", "b",394 "{ a: b }" },395 { "{ a: c }", "a", "b",396 "{ a: b }" },397 { "{ a: b }", "b", "a",398 "{ a: b, b: a }" },399 { "{ a: b }", "b", "a",400 "{ b: a, a: b }" },401 });402}403 404/* The list of tests to perform.405 */406static std::vector<std::pair<const char *, void (*)(isl::ctx)>> tests =407{408 { "space", &test_space },409 { "conversion", &test_conversion },410 { "preimage", &test_preimage },411 { "fixed power", &test_fixed_power },412 { "intersect", &test_intersect },413 { "gist", &test_gist },414 { "project out parameters", &test_project },415 { "scale", &test_scale },416 { "id-to-id", &test_id_to_id },417};418 419/* Perform some basic checks by means of the C++ bindings.420 */421int main(int argc, char **argv)422{423 int ret = EXIT_SUCCESS;424 struct isl_ctx *ctx;425 struct isl_options *options;426 427 options = isl_options_new_with_defaults();428 assert(options);429 argc = isl_options_parse(options, argc, argv, ISL_ARG_ALL);430 ctx = isl_ctx_alloc_with_options(&isl_options_args, options);431 432 try {433 for (const auto &f : tests) {434 std::cout << f.first << "\n";435 f.second(ctx);436 }437 } catch (const isl::exception &e) {438 std::cerr << e.what() << "\n";439 ret = EXIT_FAILURE;440 }441 442 isl_ctx_free(ctx);443 return ret;444}445