| 1 | /* |
| 2 | * Copyright 2011 INRIA Saclay |
| 3 | * Copyright 2012-2014 Ecole Normale Superieure |
| 4 | * Copyright 2016 Sven Verdoolaege |
| 5 | * |
| 6 | * Use of this software is governed by the MIT license |
| 7 | * |
| 8 | * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, |
| 9 | * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, |
| 10 | * 91893 Orsay, France |
| 11 | * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France |
| 12 | */ |
| 13 | |
| 14 | #include <isl/ctx.h> |
| 15 | #include <isl/val.h> |
| 16 | #include <isl_aff_private.h> |
| 17 | #include <isl/map.h> |
| 18 | #include <isl/set.h> |
| 19 | #include <isl/schedule.h> |
| 20 | #include <isl/schedule_node.h> |
| 21 | #include <isl_sort.h> |
| 22 | #include <isl/printer.h> |
| 23 | #include <isl_schedule_private.h> |
| 24 | #include <isl_schedule_tree.h> |
| 25 | #include <isl_schedule_node_private.h> |
| 26 | |
| 27 | /* Return a schedule encapsulating the given schedule tree. |
| 28 | * |
| 29 | * We currently only allow schedule trees with a domain or extension as root. |
| 30 | * |
| 31 | * The leaf field is initialized as a leaf node so that it can be |
| 32 | * used to represent leaves in the constructed schedule. |
| 33 | * The reference count is set to -1 since the isl_schedule_tree |
| 34 | * should never be freed. It is up to the (internal) users of |
| 35 | * these leaves to ensure that they are only used while the schedule |
| 36 | * is still alive. |
| 37 | */ |
| 38 | __isl_give isl_schedule *isl_schedule_from_schedule_tree(isl_ctx *ctx, |
| 39 | __isl_take isl_schedule_tree *tree) |
| 40 | { |
| 41 | enum isl_schedule_node_type type; |
| 42 | isl_schedule *schedule; |
| 43 | |
| 44 | if (!tree) |
| 45 | return NULL; |
| 46 | type = isl_schedule_tree_get_type(tree); |
| 47 | if (type != isl_schedule_node_domain && |
| 48 | type != isl_schedule_node_extension) |
| 49 | isl_die(isl_schedule_tree_get_ctx(tree), isl_error_unsupported, |
| 50 | "root of schedule tree should be a domain or extension" , |
| 51 | goto error); |
| 52 | |
| 53 | schedule = isl_calloc_type(ctx, isl_schedule); |
| 54 | if (!schedule) |
| 55 | goto error; |
| 56 | |
| 57 | schedule->ref = 1; |
| 58 | schedule->root = tree; |
| 59 | schedule->leaf = isl_schedule_tree_leaf(ctx); |
| 60 | |
| 61 | if (!schedule->leaf) |
| 62 | return isl_schedule_free(sched: schedule); |
| 63 | return schedule; |
| 64 | error: |
| 65 | isl_schedule_tree_free(tree); |
| 66 | return NULL; |
| 67 | } |
| 68 | |
| 69 | /* Return a pointer to a schedule with as single node |
| 70 | * a domain node with the given domain. |
| 71 | */ |
| 72 | __isl_give isl_schedule *isl_schedule_from_domain( |
| 73 | __isl_take isl_union_set *domain) |
| 74 | { |
| 75 | isl_ctx *ctx; |
| 76 | isl_schedule_tree *tree; |
| 77 | |
| 78 | ctx = isl_union_set_get_ctx(uset: domain); |
| 79 | tree = isl_schedule_tree_from_domain(domain); |
| 80 | return isl_schedule_from_schedule_tree(ctx, tree); |
| 81 | } |
| 82 | |
| 83 | /* Return a pointer to a schedule with as single node |
| 84 | * a domain node with an empty domain. |
| 85 | */ |
| 86 | __isl_give isl_schedule *isl_schedule_empty(__isl_take isl_space *space) |
| 87 | { |
| 88 | return isl_schedule_from_domain(domain: isl_union_set_empty(space)); |
| 89 | } |
| 90 | |
| 91 | /* Return a new reference to "sched". |
| 92 | */ |
| 93 | __isl_give isl_schedule *isl_schedule_copy(__isl_keep isl_schedule *sched) |
| 94 | { |
| 95 | if (!sched) |
| 96 | return NULL; |
| 97 | |
| 98 | sched->ref++; |
| 99 | return sched; |
| 100 | } |
| 101 | |
| 102 | /* Return an isl_schedule that is equal to "schedule" and that has only |
| 103 | * a single reference. |
| 104 | */ |
| 105 | __isl_give isl_schedule *isl_schedule_cow(__isl_take isl_schedule *schedule) |
| 106 | { |
| 107 | isl_ctx *ctx; |
| 108 | isl_schedule_tree *tree; |
| 109 | |
| 110 | if (!schedule) |
| 111 | return NULL; |
| 112 | if (schedule->ref == 1) |
| 113 | return schedule; |
| 114 | |
| 115 | ctx = isl_schedule_get_ctx(sched: schedule); |
| 116 | schedule->ref--; |
| 117 | tree = isl_schedule_tree_copy(tree: schedule->root); |
| 118 | return isl_schedule_from_schedule_tree(ctx, tree); |
| 119 | } |
| 120 | |
| 121 | __isl_null isl_schedule *isl_schedule_free(__isl_take isl_schedule *sched) |
| 122 | { |
| 123 | if (!sched) |
| 124 | return NULL; |
| 125 | |
| 126 | if (--sched->ref > 0) |
| 127 | return NULL; |
| 128 | |
| 129 | isl_schedule_tree_free(tree: sched->root); |
| 130 | isl_schedule_tree_free(tree: sched->leaf); |
| 131 | free(ptr: sched); |
| 132 | return NULL; |
| 133 | } |
| 134 | |
| 135 | /* Replace the root of "schedule" by "tree". |
| 136 | */ |
| 137 | __isl_give isl_schedule *isl_schedule_set_root( |
| 138 | __isl_take isl_schedule *schedule, __isl_take isl_schedule_tree *tree) |
| 139 | { |
| 140 | if (!schedule || !tree) |
| 141 | goto error; |
| 142 | if (schedule->root == tree) { |
| 143 | isl_schedule_tree_free(tree); |
| 144 | return schedule; |
| 145 | } |
| 146 | |
| 147 | schedule = isl_schedule_cow(schedule); |
| 148 | if (!schedule) |
| 149 | goto error; |
| 150 | isl_schedule_tree_free(tree: schedule->root); |
| 151 | schedule->root = tree; |
| 152 | |
| 153 | return schedule; |
| 154 | error: |
| 155 | isl_schedule_free(sched: schedule); |
| 156 | isl_schedule_tree_free(tree); |
| 157 | return NULL; |
| 158 | } |
| 159 | |
| 160 | isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule) |
| 161 | { |
| 162 | return schedule ? isl_schedule_tree_get_ctx(tree: schedule->leaf) : NULL; |
| 163 | } |
| 164 | |
| 165 | /* Return a pointer to the leaf of "schedule". |
| 166 | */ |
| 167 | __isl_keep isl_schedule_tree *isl_schedule_peek_leaf( |
| 168 | __isl_keep isl_schedule *schedule) |
| 169 | { |
| 170 | return schedule ? schedule->leaf : NULL; |
| 171 | } |
| 172 | |
| 173 | /* Are "schedule1" and "schedule2" obviously equal to each other? |
| 174 | */ |
| 175 | isl_bool isl_schedule_plain_is_equal(__isl_keep isl_schedule *schedule1, |
| 176 | __isl_keep isl_schedule *schedule2) |
| 177 | { |
| 178 | if (!schedule1 || !schedule2) |
| 179 | return isl_bool_error; |
| 180 | if (schedule1 == schedule2) |
| 181 | return isl_bool_true; |
| 182 | return isl_schedule_tree_plain_is_equal(tree1: schedule1->root, |
| 183 | tree2: schedule2->root); |
| 184 | } |
| 185 | |
| 186 | /* Return the (parameter) space of the schedule, i.e., the space |
| 187 | * of the root domain. |
| 188 | */ |
| 189 | __isl_give isl_space *isl_schedule_get_space( |
| 190 | __isl_keep isl_schedule *schedule) |
| 191 | { |
| 192 | enum isl_schedule_node_type type; |
| 193 | isl_space *space; |
| 194 | isl_union_set *domain; |
| 195 | |
| 196 | if (!schedule) |
| 197 | return NULL; |
| 198 | type = isl_schedule_tree_get_type(tree: schedule->root); |
| 199 | if (type != isl_schedule_node_domain) |
| 200 | isl_die(isl_schedule_get_ctx(schedule), isl_error_internal, |
| 201 | "root node not a domain node" , return NULL); |
| 202 | |
| 203 | domain = isl_schedule_tree_domain_get_domain(tree: schedule->root); |
| 204 | space = isl_union_set_get_space(uset: domain); |
| 205 | isl_union_set_free(uset: domain); |
| 206 | |
| 207 | return space; |
| 208 | } |
| 209 | |
| 210 | /* Return a pointer to the root of "schedule". |
| 211 | */ |
| 212 | __isl_give isl_schedule_node *isl_schedule_get_root( |
| 213 | __isl_keep isl_schedule *schedule) |
| 214 | { |
| 215 | isl_ctx *ctx; |
| 216 | isl_schedule_tree *tree; |
| 217 | isl_schedule_tree_list *ancestors; |
| 218 | |
| 219 | if (!schedule) |
| 220 | return NULL; |
| 221 | |
| 222 | ctx = isl_schedule_get_ctx(schedule); |
| 223 | tree = isl_schedule_tree_copy(tree: schedule->root); |
| 224 | schedule = isl_schedule_copy(sched: schedule); |
| 225 | ancestors = isl_schedule_tree_list_alloc(ctx, n: 0); |
| 226 | return isl_schedule_node_alloc(schedule, tree, ancestors, NULL); |
| 227 | } |
| 228 | |
| 229 | /* Return the domain of the root domain node of "schedule". |
| 230 | */ |
| 231 | __isl_give isl_union_set *isl_schedule_get_domain( |
| 232 | __isl_keep isl_schedule *schedule) |
| 233 | { |
| 234 | if (!schedule) |
| 235 | return NULL; |
| 236 | return isl_schedule_tree_domain_get_domain(tree: schedule->root); |
| 237 | } |
| 238 | |
| 239 | /* Traverse all nodes of "sched" in depth first preorder. |
| 240 | * |
| 241 | * If "fn" returns -1 on any of the nodes, then the traversal is aborted. |
| 242 | * If "fn" returns 0 on any of the nodes, then the subtree rooted |
| 243 | * at that node is skipped. |
| 244 | * |
| 245 | * Return 0 on success and -1 on failure. |
| 246 | */ |
| 247 | isl_stat isl_schedule_foreach_schedule_node_top_down( |
| 248 | __isl_keep isl_schedule *sched, |
| 249 | isl_bool (*fn)(__isl_keep isl_schedule_node *node, void *user), |
| 250 | void *user) |
| 251 | { |
| 252 | isl_schedule_node *node; |
| 253 | isl_stat r; |
| 254 | |
| 255 | if (!sched) |
| 256 | return isl_stat_error; |
| 257 | |
| 258 | node = isl_schedule_get_root(schedule: sched); |
| 259 | r = isl_schedule_node_foreach_descendant_top_down(node, fn, user); |
| 260 | isl_schedule_node_free(node); |
| 261 | |
| 262 | return r; |
| 263 | } |
| 264 | |
| 265 | /* Traverse the node of "sched" in depth first postorder, |
| 266 | * allowing the user to modify the visited node. |
| 267 | * The traversal continues from the node returned by the callback function. |
| 268 | * It is the responsibility of the user to ensure that this does not |
| 269 | * lead to an infinite loop. It is safest to always return a pointer |
| 270 | * to the same position (same ancestors and child positions) as the input node. |
| 271 | */ |
| 272 | __isl_give isl_schedule *isl_schedule_map_schedule_node_bottom_up( |
| 273 | __isl_take isl_schedule *schedule, |
| 274 | __isl_give isl_schedule_node *(*fn)( |
| 275 | __isl_take isl_schedule_node *node, void *user), void *user) |
| 276 | { |
| 277 | isl_schedule_node *node; |
| 278 | |
| 279 | node = isl_schedule_get_root(schedule); |
| 280 | isl_schedule_free(sched: schedule); |
| 281 | |
| 282 | node = isl_schedule_node_map_descendant_bottom_up(node, fn, user); |
| 283 | schedule = isl_schedule_node_get_schedule(node); |
| 284 | isl_schedule_node_free(node); |
| 285 | |
| 286 | return schedule; |
| 287 | } |
| 288 | |
| 289 | /* Wrapper around isl_schedule_node_reset_user for use as |
| 290 | * an isl_schedule_map_schedule_node_bottom_up callback. |
| 291 | */ |
| 292 | static __isl_give isl_schedule_node *reset_user( |
| 293 | __isl_take isl_schedule_node *node, void *user) |
| 294 | { |
| 295 | return isl_schedule_node_reset_user(node); |
| 296 | } |
| 297 | |
| 298 | /* Reset the user pointer on all identifiers of parameters and tuples |
| 299 | * in the schedule "schedule". |
| 300 | */ |
| 301 | __isl_give isl_schedule *isl_schedule_reset_user( |
| 302 | __isl_take isl_schedule *schedule) |
| 303 | { |
| 304 | return isl_schedule_map_schedule_node_bottom_up(schedule, fn: &reset_user, |
| 305 | NULL); |
| 306 | } |
| 307 | |
| 308 | /* Wrapper around isl_schedule_node_align_params for use as |
| 309 | * an isl_schedule_map_schedule_node_bottom_up callback. |
| 310 | */ |
| 311 | static __isl_give isl_schedule_node *align_params( |
| 312 | __isl_take isl_schedule_node *node, void *user) |
| 313 | { |
| 314 | isl_space *space = user; |
| 315 | |
| 316 | return isl_schedule_node_align_params(node, space: isl_space_copy(space)); |
| 317 | } |
| 318 | |
| 319 | /* Align the parameters of all nodes in schedule "schedule" |
| 320 | * to those of "space". |
| 321 | */ |
| 322 | __isl_give isl_schedule *isl_schedule_align_params( |
| 323 | __isl_take isl_schedule *schedule, __isl_take isl_space *space) |
| 324 | { |
| 325 | schedule = isl_schedule_map_schedule_node_bottom_up(schedule, |
| 326 | fn: &align_params, user: space); |
| 327 | isl_space_free(space); |
| 328 | return schedule; |
| 329 | } |
| 330 | |
| 331 | /* Wrapper around isl_schedule_node_pullback_union_pw_multi_aff for use as |
| 332 | * an isl_schedule_map_schedule_node_bottom_up callback. |
| 333 | */ |
| 334 | static __isl_give isl_schedule_node *pullback_upma( |
| 335 | __isl_take isl_schedule_node *node, void *user) |
| 336 | { |
| 337 | isl_union_pw_multi_aff *upma = user; |
| 338 | |
| 339 | return isl_schedule_node_pullback_union_pw_multi_aff(node, |
| 340 | upma: isl_union_pw_multi_aff_copy(upma)); |
| 341 | } |
| 342 | |
| 343 | /* Compute the pullback of "schedule" by the function represented by "upma". |
| 344 | * In other words, plug in "upma" in the iteration domains of "schedule". |
| 345 | * |
| 346 | * The schedule tree is not allowed to contain any expansion nodes. |
| 347 | */ |
| 348 | __isl_give isl_schedule *isl_schedule_pullback_union_pw_multi_aff( |
| 349 | __isl_take isl_schedule *schedule, |
| 350 | __isl_take isl_union_pw_multi_aff *upma) |
| 351 | { |
| 352 | schedule = isl_schedule_map_schedule_node_bottom_up(schedule, |
| 353 | fn: &pullback_upma, user: upma); |
| 354 | isl_union_pw_multi_aff_free(upma); |
| 355 | return schedule; |
| 356 | } |
| 357 | |
| 358 | /* Expand the schedule "schedule" by extending all leaves |
| 359 | * with an expansion node with as subtree the tree of "expansion". |
| 360 | * The expansion of the expansion node is determined by "contraction" |
| 361 | * and the domain of "expansion". That is, the domain of "expansion" |
| 362 | * is contracted according to "contraction". |
| 363 | * |
| 364 | * Call isl_schedule_node_expand after extracting the required |
| 365 | * information from "expansion". |
| 366 | */ |
| 367 | __isl_give isl_schedule *isl_schedule_expand(__isl_take isl_schedule *schedule, |
| 368 | __isl_take isl_union_pw_multi_aff *contraction, |
| 369 | __isl_take isl_schedule *expansion) |
| 370 | { |
| 371 | isl_union_set *domain; |
| 372 | isl_schedule_node *node; |
| 373 | isl_schedule_tree *tree; |
| 374 | |
| 375 | domain = isl_schedule_get_domain(schedule: expansion); |
| 376 | |
| 377 | node = isl_schedule_get_root(schedule: expansion); |
| 378 | node = isl_schedule_node_child(node, pos: 0); |
| 379 | tree = isl_schedule_node_get_tree(node); |
| 380 | isl_schedule_node_free(node); |
| 381 | isl_schedule_free(sched: expansion); |
| 382 | |
| 383 | node = isl_schedule_get_root(schedule); |
| 384 | isl_schedule_free(sched: schedule); |
| 385 | node = isl_schedule_node_expand(node, contraction, domain, tree); |
| 386 | schedule = isl_schedule_node_get_schedule(node); |
| 387 | isl_schedule_node_free(node); |
| 388 | |
| 389 | return schedule; |
| 390 | } |
| 391 | |
| 392 | /* Intersect the domain of the schedule "schedule" with "domain". |
| 393 | * The root of "schedule" is required to be a domain node. |
| 394 | */ |
| 395 | __isl_give isl_schedule *isl_schedule_intersect_domain( |
| 396 | __isl_take isl_schedule *schedule, __isl_take isl_union_set *domain) |
| 397 | { |
| 398 | enum isl_schedule_node_type root_type; |
| 399 | isl_schedule_node *node; |
| 400 | |
| 401 | if (!schedule || !domain) |
| 402 | goto error; |
| 403 | |
| 404 | root_type = isl_schedule_tree_get_type(tree: schedule->root); |
| 405 | if (root_type != isl_schedule_node_domain) |
| 406 | isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid, |
| 407 | "root node must be a domain node" , goto error); |
| 408 | |
| 409 | node = isl_schedule_get_root(schedule); |
| 410 | isl_schedule_free(sched: schedule); |
| 411 | node = isl_schedule_node_domain_intersect_domain(node, domain); |
| 412 | schedule = isl_schedule_node_get_schedule(node); |
| 413 | isl_schedule_node_free(node); |
| 414 | |
| 415 | return schedule; |
| 416 | error: |
| 417 | isl_schedule_free(sched: schedule); |
| 418 | isl_union_set_free(uset: domain); |
| 419 | return NULL; |
| 420 | } |
| 421 | |
| 422 | /* Replace the domain of the schedule "schedule" with the gist |
| 423 | * of the original domain with respect to the parameter domain "context". |
| 424 | */ |
| 425 | __isl_give isl_schedule *isl_schedule_gist_domain_params( |
| 426 | __isl_take isl_schedule *schedule, __isl_take isl_set *context) |
| 427 | { |
| 428 | enum isl_schedule_node_type root_type; |
| 429 | isl_schedule_node *node; |
| 430 | |
| 431 | if (!schedule || !context) |
| 432 | goto error; |
| 433 | |
| 434 | root_type = isl_schedule_tree_get_type(tree: schedule->root); |
| 435 | if (root_type != isl_schedule_node_domain) |
| 436 | isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid, |
| 437 | "root node must be a domain node" , goto error); |
| 438 | |
| 439 | node = isl_schedule_get_root(schedule); |
| 440 | isl_schedule_free(sched: schedule); |
| 441 | node = isl_schedule_node_domain_gist_params(node, context); |
| 442 | schedule = isl_schedule_node_get_schedule(node); |
| 443 | isl_schedule_node_free(node); |
| 444 | |
| 445 | return schedule; |
| 446 | error: |
| 447 | isl_schedule_free(sched: schedule); |
| 448 | isl_set_free(set: context); |
| 449 | return NULL; |
| 450 | } |
| 451 | |
| 452 | /* Return an isl_union_map representation of the schedule. In particular, |
| 453 | * return an isl_union_map corresponding to the subtree schedule of the child |
| 454 | * of the root domain node. That is, we do not intersect the domain |
| 455 | * of the returned isl_union_map with the domain constraints. |
| 456 | */ |
| 457 | __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched) |
| 458 | { |
| 459 | enum isl_schedule_node_type type; |
| 460 | isl_schedule_node *node; |
| 461 | isl_union_map *umap; |
| 462 | |
| 463 | if (!sched) |
| 464 | return NULL; |
| 465 | type = isl_schedule_tree_get_type(tree: sched->root); |
| 466 | if (type != isl_schedule_node_domain) |
| 467 | isl_die(isl_schedule_get_ctx(sched), isl_error_internal, |
| 468 | "root node not a domain node" , return NULL); |
| 469 | |
| 470 | node = isl_schedule_get_root(schedule: sched); |
| 471 | node = isl_schedule_node_child(node, pos: 0); |
| 472 | umap = isl_schedule_node_get_subtree_schedule_union_map(node); |
| 473 | isl_schedule_node_free(node); |
| 474 | |
| 475 | return umap; |
| 476 | } |
| 477 | |
| 478 | /* Insert a band node with partial schedule "partial" between the domain |
| 479 | * root node of "schedule" and its single child. |
| 480 | * Return a pointer to the updated schedule. |
| 481 | * |
| 482 | * If any of the nodes in the tree depend on the set of outer band nodes |
| 483 | * then we refuse to insert the band node. |
| 484 | */ |
| 485 | __isl_give isl_schedule *isl_schedule_insert_partial_schedule( |
| 486 | __isl_take isl_schedule *schedule, |
| 487 | __isl_take isl_multi_union_pw_aff *partial) |
| 488 | { |
| 489 | isl_schedule_node *node; |
| 490 | int anchored; |
| 491 | |
| 492 | node = isl_schedule_get_root(schedule); |
| 493 | isl_schedule_free(sched: schedule); |
| 494 | if (!node) |
| 495 | goto error; |
| 496 | if (isl_schedule_node_get_type(node) != isl_schedule_node_domain) |
| 497 | isl_die(isl_schedule_node_get_ctx(node), isl_error_internal, |
| 498 | "root node not a domain node" , goto error); |
| 499 | |
| 500 | node = isl_schedule_node_child(node, pos: 0); |
| 501 | anchored = isl_schedule_node_is_subtree_anchored(node); |
| 502 | if (anchored < 0) |
| 503 | goto error; |
| 504 | if (anchored) |
| 505 | isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid, |
| 506 | "cannot insert band node in anchored subtree" , |
| 507 | goto error); |
| 508 | node = isl_schedule_node_insert_partial_schedule(node, schedule: partial); |
| 509 | |
| 510 | schedule = isl_schedule_node_get_schedule(node); |
| 511 | isl_schedule_node_free(node); |
| 512 | |
| 513 | return schedule; |
| 514 | error: |
| 515 | isl_schedule_node_free(node); |
| 516 | isl_multi_union_pw_aff_free(multi: partial); |
| 517 | return NULL; |
| 518 | } |
| 519 | |
| 520 | /* Insert a context node with constraints "context" between the domain |
| 521 | * root node of "schedule" and its single child. |
| 522 | * Return a pointer to the updated schedule. |
| 523 | */ |
| 524 | __isl_give isl_schedule *isl_schedule_insert_context( |
| 525 | __isl_take isl_schedule *schedule, __isl_take isl_set *context) |
| 526 | { |
| 527 | isl_schedule_node *node; |
| 528 | |
| 529 | node = isl_schedule_get_root(schedule); |
| 530 | isl_schedule_free(sched: schedule); |
| 531 | node = isl_schedule_node_child(node, pos: 0); |
| 532 | node = isl_schedule_node_insert_context(node, context); |
| 533 | schedule = isl_schedule_node_get_schedule(node); |
| 534 | isl_schedule_node_free(node); |
| 535 | |
| 536 | return schedule; |
| 537 | } |
| 538 | |
| 539 | /* Insert a guard node with constraints "guard" between the domain |
| 540 | * root node of "schedule" and its single child. |
| 541 | * Return a pointer to the updated schedule. |
| 542 | */ |
| 543 | __isl_give isl_schedule *isl_schedule_insert_guard( |
| 544 | __isl_take isl_schedule *schedule, __isl_take isl_set *guard) |
| 545 | { |
| 546 | isl_schedule_node *node; |
| 547 | |
| 548 | node = isl_schedule_get_root(schedule); |
| 549 | isl_schedule_free(sched: schedule); |
| 550 | node = isl_schedule_node_child(node, pos: 0); |
| 551 | node = isl_schedule_node_insert_guard(node, context: guard); |
| 552 | schedule = isl_schedule_node_get_schedule(node); |
| 553 | isl_schedule_node_free(node); |
| 554 | |
| 555 | return schedule; |
| 556 | } |
| 557 | |
| 558 | /* Return a tree with as top-level node a filter corresponding to "filter" and |
| 559 | * as child, the (single) child of "tree". |
| 560 | * However, if this single child is of type "type", then the filter is inserted |
| 561 | * in the children of this single child instead. |
| 562 | */ |
| 563 | static __isl_give isl_schedule_tree *insert_filter_in_child_of_type( |
| 564 | __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter, |
| 565 | enum isl_schedule_node_type type) |
| 566 | { |
| 567 | if (!isl_schedule_tree_has_children(tree)) { |
| 568 | isl_schedule_tree_free(tree); |
| 569 | return isl_schedule_tree_from_filter(filter); |
| 570 | } else { |
| 571 | tree = isl_schedule_tree_child(tree, pos: 0); |
| 572 | } |
| 573 | |
| 574 | if (isl_schedule_tree_get_type(tree) == type) |
| 575 | tree = isl_schedule_tree_children_insert_filter(tree, filter); |
| 576 | else |
| 577 | tree = isl_schedule_tree_insert_filter(tree, filter); |
| 578 | |
| 579 | return tree; |
| 580 | } |
| 581 | |
| 582 | /* Construct a schedule that combines the schedules "schedule1" and "schedule2" |
| 583 | * with a top-level node (underneath the domain node) of type "type", |
| 584 | * either isl_schedule_node_sequence or isl_schedule_node_set. |
| 585 | * The domains of the two schedules are assumed to be disjoint. |
| 586 | * |
| 587 | * The new schedule has as domain the union of the domains of the two |
| 588 | * schedules. The child of the domain node is a node of type "type" |
| 589 | * with two filters corresponding to the domains of the input schedules. |
| 590 | * If one (or both) of the top-level nodes of the two schedules is itself |
| 591 | * of type "type", then the filter is pushed into the children of that |
| 592 | * node and the sequence or set is flattened. |
| 593 | */ |
| 594 | __isl_give isl_schedule *isl_schedule_pair(enum isl_schedule_node_type type, |
| 595 | __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2) |
| 596 | { |
| 597 | int disjoint; |
| 598 | isl_ctx *ctx; |
| 599 | enum isl_schedule_node_type root_type; |
| 600 | isl_schedule_tree *tree1, *tree2; |
| 601 | isl_union_set *filter1, *filter2, *domain; |
| 602 | |
| 603 | if (!schedule1 || !schedule2) |
| 604 | goto error; |
| 605 | |
| 606 | root_type = isl_schedule_tree_get_type(tree: schedule1->root); |
| 607 | if (root_type != isl_schedule_node_domain) |
| 608 | isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal, |
| 609 | "root node not a domain node" , goto error); |
| 610 | root_type = isl_schedule_tree_get_type(tree: schedule2->root); |
| 611 | if (root_type != isl_schedule_node_domain) |
| 612 | isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal, |
| 613 | "root node not a domain node" , goto error); |
| 614 | |
| 615 | ctx = isl_schedule_get_ctx(schedule: schedule1); |
| 616 | tree1 = isl_schedule_tree_copy(tree: schedule1->root); |
| 617 | filter1 = isl_schedule_tree_domain_get_domain(tree: tree1); |
| 618 | tree2 = isl_schedule_tree_copy(tree: schedule2->root); |
| 619 | filter2 = isl_schedule_tree_domain_get_domain(tree: tree2); |
| 620 | |
| 621 | isl_schedule_free(sched: schedule1); |
| 622 | isl_schedule_free(sched: schedule2); |
| 623 | |
| 624 | disjoint = isl_union_set_is_disjoint(uset1: filter1, uset2: filter2); |
| 625 | if (disjoint < 0) |
| 626 | filter1 = isl_union_set_free(uset: filter1); |
| 627 | if (!disjoint) |
| 628 | isl_die(ctx, isl_error_invalid, |
| 629 | "schedule domains not disjoint" , |
| 630 | filter1 = isl_union_set_free(filter1)); |
| 631 | |
| 632 | domain = isl_union_set_union(uset1: isl_union_set_copy(uset: filter1), |
| 633 | uset2: isl_union_set_copy(uset: filter2)); |
| 634 | filter1 = isl_union_set_gist(uset: filter1, context: isl_union_set_copy(uset: domain)); |
| 635 | filter2 = isl_union_set_gist(uset: filter2, context: isl_union_set_copy(uset: domain)); |
| 636 | |
| 637 | tree1 = insert_filter_in_child_of_type(tree: tree1, filter: filter1, type); |
| 638 | tree2 = insert_filter_in_child_of_type(tree: tree2, filter: filter2, type); |
| 639 | |
| 640 | tree1 = isl_schedule_tree_from_pair(type, tree1, tree2); |
| 641 | tree1 = isl_schedule_tree_insert_domain(tree: tree1, domain); |
| 642 | |
| 643 | return isl_schedule_from_schedule_tree(ctx, tree: tree1); |
| 644 | error: |
| 645 | isl_schedule_free(sched: schedule1); |
| 646 | isl_schedule_free(sched: schedule2); |
| 647 | return NULL; |
| 648 | } |
| 649 | |
| 650 | /* Construct a schedule that combines the schedules "schedule1" and "schedule2" |
| 651 | * through a sequence node. |
| 652 | * The domains of the input schedules are assumed to be disjoint. |
| 653 | */ |
| 654 | __isl_give isl_schedule *isl_schedule_sequence( |
| 655 | __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2) |
| 656 | { |
| 657 | return isl_schedule_pair(type: isl_schedule_node_sequence, |
| 658 | schedule1, schedule2); |
| 659 | } |
| 660 | |
| 661 | /* Construct a schedule that combines the schedules "schedule1" and "schedule2" |
| 662 | * through a set node. |
| 663 | * The domains of the input schedules are assumed to be disjoint. |
| 664 | */ |
| 665 | __isl_give isl_schedule *isl_schedule_set( |
| 666 | __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2) |
| 667 | { |
| 668 | return isl_schedule_pair(type: isl_schedule_node_set, schedule1, schedule2); |
| 669 | } |
| 670 | |
| 671 | /* Print "schedule" to "p". |
| 672 | */ |
| 673 | __isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p, |
| 674 | __isl_keep isl_schedule *schedule) |
| 675 | { |
| 676 | if (!schedule) |
| 677 | return isl_printer_free(printer: p); |
| 678 | |
| 679 | return isl_printer_print_schedule_tree(p, tree: schedule->root); |
| 680 | } |
| 681 | |
| 682 | #undef BASE |
| 683 | #define BASE schedule |
| 684 | #include <print_templ_yaml.c> |
| 685 | |