polly/lib/External/isl/isl_test_cpp-generic.cc

   1 /* Copyright 2016-2017 Tobias Grosser
   2  *
   3  * Use of this software is governed by the MIT license
   4  *
   5  * Written by Tobias Grosser, Weststrasse 47, CH-8003, Zurich
   6  */
   7
   8 #ifndef IS_TRUE
   9 #define IS_TRUE(b)      (b)
  10 #endif
  11 #ifndef SIZE_VAL
  12 #define SIZE_VAL(s)     (s)
  13 #endif
  14
  15 /* Test the pointer interface for interaction between isl C and C++ types.
  16  *
  17  * This tests:
  18  * - construction from an isl C object
  19  * - check that constructed objects are non-null
  20  * - get a non-owned C pointer from an isl C++ object usable in __isl_keep
  21  *   methods
  22  * - use copy to get an owned C pointer from an isl C++ object which is usable
  23  *   in __isl_take methods. Verify that the original C++ object retains a valid
  24  *   pointer.
  25  * - use release to get an owned C pointer from an isl C++ object which is
  26  *   usable in __isl_take methods. Verify that the original C++ object gave up
  27  *   its pointer and now is null.
  28  */
  29 void test_pointer(isl::ctx ctx)
  30 {
  31         isl_set *c_empty = isl_set_read_from_str(ctx.get(), "{ : false }");
  32         isl::set empty = isl::manage(c_empty);
  33         assert(IS_TRUE(empty.is_empty()));
  34         assert(isl_set_is_empty(empty.get()));
  35
  36         assert(!empty.is_null());
  37         isl_set_free(empty.copy());
  38         assert(!empty.is_null());
  39         isl_set_free(empty.release());
  40         assert(empty.is_null());
  41 }
  42
  43 /* Test that isl objects can be constructed.
  44  *
  45  * This tests:
  46  *  - construction of a null object
  47  *  - construction from a string
  48  *  - construction from an integer
  49  *  - static constructor without a parameter
  50  *  - conversion construction (implicit)
  51  *  - conversion construction (explicit)
  52  *  - construction of empty union set
  53  *
  54  *  The tests to construct from integers and strings cover functionality that
  55  *  is also tested in the parameter type tests, but here we verify that
  56  *  multiple overloaded constructors are available and that overload resolution
  57  *  works as expected.
  58  *
  59  *  Construction from an isl C pointer is tested in test_pointer.
  60  */
  61 void test_constructors(isl::ctx ctx)
  62 {
  63         isl::val null;
  64         assert(null.is_null());
  65
  66         isl::val zero_from_str = isl::val(ctx, "0");
  67         assert(IS_TRUE(zero_from_str.is_zero()));
  68
  69         isl::val zero_int_con = isl::val(ctx, 0);
  70         assert(IS_TRUE(zero_int_con.is_zero()));
  71
  72         isl::val zero_static_con = isl::val::zero(ctx);
  73         assert(IS_TRUE(zero_static_con.is_zero()));
  74
  75         isl::basic_set bs(ctx, "{ [1] }");
  76         isl::set result(ctx, "{ [1] }");
  77         isl::set s = bs;
  78         assert(IS_TRUE(s.is_equal(result)));
  79         isl::set s2(bs);
  80         assert(IS_TRUE(s.unite(s2).is_equal(result)));
  81
  82         isl::union_set us(ctx, "{ A[1]; B[2, 3] }");
  83         isl::union_set empty = isl::union_set::empty(ctx);
  84         assert(IS_TRUE(us.is_equal(us.unite(empty))));
  85 }
  86
  87 /* Test integer function parameters.
  88  *
  89  * Verify that extreme values and zero work.
  90  */
  91 void test_parameters_int(isl::ctx ctx)
  92 {
  93         isl::val long_max_str(ctx, std::to_string(LONG_MAX));
  94         isl::val long_max_int(ctx, LONG_MAX);
  95         assert(IS_TRUE(long_max_str.eq(long_max_int)));
  96
  97         isl::val long_min_str(ctx, std::to_string(LONG_MIN));
  98         isl::val long_min_int(ctx, LONG_MIN);
  99         assert(IS_TRUE(long_min_str.eq(long_min_int)));
 100
 101         isl::val long_zero_str = isl::val(ctx, std::to_string(0));
 102         isl::val long_zero_int = isl::val(ctx, 0);
 103         assert(IS_TRUE(long_zero_str.eq(long_zero_int)));
 104 }
 105
 106 /* Test isl objects parameters.
 107  *
 108  * Verify that isl objects can be passed as lvalue and rvalue parameters.
 109  * Also verify that isl object parameters are automatically type converted if
 110  * there is an inheritance relation. Finally, test function calls without
 111  * any additional parameters, apart from the isl object on which
 112  * the method is called.
 113  */
 114 void test_parameters_obj(isl::ctx ctx)
 115 {
 116         isl::set a(ctx, "{ [0] }");
 117         isl::set b(ctx, "{ [1] }");
 118         isl::set c(ctx, "{ [2] }");
 119         isl::set expected(ctx, "{ [i] : 0 <= i <= 2 }");
 120
 121         isl::set tmp = a.unite(b);
 122         isl::set res_lvalue_param = tmp.unite(c);
 123         assert(IS_TRUE(res_lvalue_param.is_equal(expected)));
 124
 125         isl::set res_rvalue_param = a.unite(b).unite(c);
 126         assert(IS_TRUE(res_rvalue_param.is_equal(expected)));
 127
 128         isl::basic_set a2(ctx, "{ [0] }");
 129         assert(IS_TRUE(a.is_equal(a2)));
 130
 131         isl::val two(ctx, 2);
 132         isl::val half(ctx, "1/2");
 133         isl::val res_only_this_param = two.inv();
 134         assert(IS_TRUE(res_only_this_param.eq(half)));
 135 }
 136
 137 /* Test different kinds of parameters to be passed to functions.
 138  *
 139  * This includes integer and isl C++ object parameters.
 140  */
 141 void test_parameters(isl::ctx ctx)
 142 {
 143         test_parameters_int(ctx);
 144         test_parameters_obj(ctx);
 145 }
 146
 147 /* Test that isl objects are returned correctly.
 148  *
 149  * This only tests that after combining two objects, the result is successfully
 150  * returned.
 151  */
 152 void test_return_obj(isl::ctx ctx)
 153 {
 154         isl::val one(ctx, "1");
 155         isl::val two(ctx, "2");
 156         isl::val three(ctx, "3");
 157
 158         isl::val res = one.add(two);
 159
 160         assert(IS_TRUE(res.eq(three)));
 161 }
 162
 163 /* Test that integer values are returned correctly.
 164  */
 165 void test_return_int(isl::ctx ctx)
 166 {
 167         isl::val one(ctx, "1");
 168         isl::val neg_one(ctx, "-1");
 169         isl::val zero(ctx, "0");
 170
 171         assert(one.sgn() > 0);
 172         assert(neg_one.sgn() < 0);
 173         assert(zero.sgn() == 0);
 174 }
 175
 176 /* Test that strings are returned correctly.
 177  * Do so by calling overloaded isl::ast_build::from_expr methods.
 178  */
 179 void test_return_string(isl::ctx ctx)
 180 {
 181         isl::set context(ctx, "[n] -> { : }");
 182         isl::ast_build build = isl::ast_build::from_context(context);
 183         isl::pw_aff pw_aff(ctx, "[n] -> { [n] }");
 184         isl::set set(ctx, "[n] -> { : n >= 0 }");
 185
 186         isl::ast_expr expr = build.expr_from(pw_aff);
 187         const char *expected_string = "n";
 188         assert(expected_string == expr.to_C_str());
 189
 190         expr = build.expr_from(set);
 191         expected_string = "n >= 0";
 192         assert(expected_string == expr.to_C_str());
 193 }
 194
 195 /* Test the functionality of "every" functions
 196  * that does not depend on the type of C++ bindings.
 197  */
 198 static void test_every_generic(isl::ctx ctx)
 199 {
 200         isl::union_set us(ctx, "{ A[i]; B[j] }");
 201
 202         auto is_empty = [] (isl::set s) {
 203                 return s.is_empty();
 204         };
 205         assert(!IS_TRUE(us.every_set(is_empty)));
 206
 207         auto is_non_empty = [] (isl::set s) {
 208                 return !s.is_empty();
 209         };
 210         assert(IS_TRUE(us.every_set(is_non_empty)));
 211
 212         auto in_A = [] (isl::set s) {
 213                 return s.is_subset(isl::set(s.ctx(), "{ A[x] }"));
 214         };
 215         assert(!IS_TRUE(us.every_set(in_A)));
 216
 217         auto not_in_A = [] (isl::set s) {
 218                 return !s.is_subset(isl::set(s.ctx(), "{ A[x] }"));
 219         };
 220         assert(!IS_TRUE(us.every_set(not_in_A)));
 221 }
 222
 223 /* Check basic construction of spaces.
 224  */
 225 static void test_space(isl::ctx ctx)
 226 {
 227         isl::space unit = isl::space::unit(ctx);
 228         isl::space set_space = unit.add_named_tuple("A", 3);
 229         isl::space map_space = set_space.add_named_tuple("B", 2);
 230
 231         isl::set set = isl::set::universe(set_space);
 232         isl::map map = isl::map::universe(map_space);
 233         assert(IS_TRUE(set.is_equal(isl::set(ctx, "{ A[*,*,*] }"))));
 234         assert(IS_TRUE(map.is_equal(isl::map(ctx, "{ A[*,*,*] -> B[*,*] }"))));
 235 }
 236
 237 /* Construct a simple schedule tree with an outer sequence node and
 238  * a single-dimensional band node in each branch, with one of them
 239  * marked coincident.
 240  */
 241 static isl::schedule construct_schedule_tree(isl::ctx ctx)
 242 {
 243         isl::union_set A(ctx, "{ A[i] : 0 <= i < 10 }");
 244         isl::union_set B(ctx, "{ B[i] : 0 <= i < 20 }");
 245
 246         auto node = isl::schedule_node::from_domain(A.unite(B));
 247         node = node.child(0);
 248
 249         isl::union_set_list filters(ctx, 0);
 250         filters = filters.add(A).add(B);
 251         node = node.insert_sequence(filters);
 252
 253         isl::multi_union_pw_aff f_A(ctx, "[ { A[i] -> [i] } ]");
 254         node = node.child(0);
 255         node = node.child(0);
 256         node = node.insert_partial_schedule(f_A);
 257         auto band = node.as<isl::schedule_node_band>();
 258         band = band.member_set_coincident(0, true);
 259         node = band.ancestor(2);
 260
 261         isl::multi_union_pw_aff f_B(ctx, "[ { B[i] -> [i] } ]");
 262         node = node.child(1);
 263         node = node.child(0);
 264         node = node.insert_partial_schedule(f_B);
 265         node = node.ancestor(2);
 266
 267         return node.schedule();
 268 }
 269
 270 /* Test basic schedule tree functionality that is independent
 271  * of the type of bindings.
 272  *
 273  * In particular, create a simple schedule tree and
 274  * - check that the root node is a domain node
 275  * - check that an object of a subclass can be used as one of the superclass
 276  * - test map_descendant_bottom_up in the successful case
 277  */
 278 static isl::schedule_node test_schedule_tree_generic(isl::ctx ctx)
 279 {
 280         auto schedule = construct_schedule_tree(ctx);
 281         auto root = schedule.root();
 282
 283         assert(IS_TRUE(root.isa<isl::schedule_node_domain>()));
 284         root = root.as<isl::schedule_node_domain>().child(0).parent();
 285
 286         int count = 0;
 287         auto inc_count = [&count](isl::schedule_node node) {
 288                 count++;
 289                 return node;
 290         };
 291         root = root.map_descendant_bottom_up(inc_count);
 292         assert(count == 8);
 293
 294         return root;
 295 }
 296
 297 /* Test marking band members for unrolling.
 298  * "schedule" is the schedule created by construct_schedule_tree.
 299  * It schedules two statements, with 10 and 20 instances, respectively.
 300  * Unrolling all band members therefore results in 30 at-domain calls
 301  * by the AST generator.
 302  */
 303 static void test_ast_build_unroll(isl::schedule schedule)
 304 {
 305         auto root = schedule.root();
 306         auto mark_unroll = [](isl::schedule_node node) {
 307                 if (IS_TRUE(node.isa<isl::schedule_node_band>())) {
 308                         auto band = node.as<isl::schedule_node_band>();
 309                         node = band.member_set_ast_loop_unroll(0);
 310                 }
 311                 return node;
 312         };
 313         root = root.map_descendant_bottom_up(mark_unroll);
 314         schedule = root.schedule();
 315
 316         int count_ast = 0;
 317         auto inc_count_ast =
 318             [&count_ast](isl::ast_node node, isl::ast_build build) {
 319                 count_ast++;
 320                 return node;
 321         };
 322         auto build = isl::ast_build(schedule.ctx());
 323         build = build.set_at_each_domain(inc_count_ast);
 324         auto ast = build.node_from(schedule);
 325         assert(count_ast == 30);
 326 }
 327
 328 /* Test basic AST generation from a schedule tree that is independent
 329  * of the type of bindings.
 330  *
 331  * In particular, create a simple schedule tree and
 332  * - generate an AST from the schedule tree
 333  * - test at_each_domain in the successful case
 334  * - test unrolling
 335  */
 336 static isl::schedule test_ast_build_generic(isl::ctx ctx)
 337 {
 338         auto schedule = construct_schedule_tree(ctx);
 339
 340         int count_ast = 0;
 341         auto inc_count_ast =
 342             [&count_ast](isl::ast_node node, isl::ast_build build) {
 343                 count_ast++;
 344                 return node;
 345         };
 346         auto build = isl::ast_build(ctx);
 347         auto build_copy = build.set_at_each_domain(inc_count_ast);
 348         auto ast = build.node_from(schedule);
 349         assert(count_ast == 0);
 350         count_ast = 0;
 351         ast = build_copy.node_from(schedule);
 352         assert(count_ast == 2);
 353         build = build_copy;
 354         count_ast = 0;
 355         ast = build.node_from(schedule);
 356         assert(count_ast == 2);
 357
 358         test_ast_build_unroll(schedule);
 359
 360         return schedule;
 361 }
 362
 363 /* Test basic AST expression generation from an affine expression.
 364  */
 365 static void test_ast_build_expr(isl::ctx ctx)
 366 {
 367         isl::pw_aff pa(ctx, "[n] -> { [n + 1] }");
 368         isl::ast_build build = isl::ast_build::from_context(pa.domain());
 369
 370         auto expr = build.expr_from(pa);
 371         auto op = expr.as<isl::ast_expr_op>();
 372         assert(IS_TRUE(op.isa<isl::ast_expr_op_add>()));
 373         assert(SIZE_VAL(op.n_arg()) == 2);
 374 }