gpu_tree.c

   1 /*
   2  * Copyright 2013      Ecole Normale Superieure
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege,
   7  * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
   8  */
   9
  10 #include <string.h>
  11
  12 #include <isl/set.h>
  13 #include <isl/union_set.h>
  14
  15 #include "gpu_tree.h"
  16
  17 /* The functions in this file are used to navigate part of a schedule tree
  18  * that is mapped to blocks.  Initially, this part consists of a linear
  19  * branch segment with a mark node with name "kernel" on the outer end
  20  * and a mark node with name "thread" on the inner end.
  21  * During the mapping to blocks, branching may be introduced, but only
  22  * one of the elements in each sequence contains the "thread" mark.
  23  * The filter of this element (and only this filter) contains
  24  * domain elements identified by the "core" argument of the functions
  25  * that move down this tree.
  26  *
  27  * Synchronization statements have a name that starts with "sync" and
  28  * a user pointer pointing to the kernel that contains the synchronization.
  29  * The functions inserting or detecting synchronizations take a ppcg_kernel
  30  * argument to be able to create or identify such statements.
  31  * They may also use two fields in this structure, the "core" field
  32  * to move around in the tree and the "n_sync" field to make sure that
  33  * each synchronization has a different name (within the kernel).
  34  */
  35
  36 /* Is "node" a mark node with an identifier called "name"?
  37  */
  38 static int is_marked(__isl_keep isl_schedule_node *node, const char *name)
  39 {
  40         isl_id *mark;
  41         int has_name;
  42
  43         if (!node)
  44                 return -1;
  45
  46         if (isl_schedule_node_get_type(node) != isl_schedule_node_mark)
  47                 return 0;
  48
  49         mark = isl_schedule_node_mark_get_id(node);
  50         if (!mark)
  51                 return -1;
  52
  53         has_name = !strcmp(isl_id_get_name(mark), name);
  54         isl_id_free(mark);
  55
  56         return has_name;
  57 }
  58
  59 /* Is "node" a mark node with an identifier called "kernel"?
  60  */
  61 int gpu_tree_node_is_kernel(__isl_keep isl_schedule_node *node)
  62 {
  63         return is_marked(node, "kernel");
  64 }
  65
  66 /* Is "node" a mark node with an identifier called "thread"?
  67  */
  68 static int node_is_thread(__isl_keep isl_schedule_node *node)
  69 {
  70         return is_marked(node, "thread");
  71 }
  72
  73 /* Assuming "node" is a filter node, does it correspond to the branch
  74  * that contains the "thread" mark, i.e., does it contain any elements
  75  * in "core"?
  76  */
  77 static int node_is_core(__isl_keep isl_schedule_node *node,
  78         __isl_keep isl_union_set *core)
  79 {
  80         int disjoint;
  81         isl_union_set *filter;
  82
  83         filter = isl_schedule_node_filter_get_filter(node);
  84         disjoint = isl_union_set_is_disjoint(filter, core);
  85         isl_union_set_free(filter);
  86         if (disjoint < 0)
  87                 return -1;
  88
  89         return !disjoint;
  90 }
  91
  92 /* Move to the only child of "node" that has the "thread" mark as descendant,
  93  * where the branch containing this mark is identified by the domain elements
  94  * in "core".
  95  *
  96  * If "node" is not a sequence, then it only has one child and we move
  97  * to that single child.
  98  * Otherwise, we check each of the filters in the children, pick
  99  * the one that corresponds to "core" and return a pointer to the child
 100  * of the filter node.
 101  */
 102 static __isl_give isl_schedule_node *core_child(
 103         __isl_take isl_schedule_node *node, __isl_keep isl_union_set *core)
 104 {
 105         int i, n;
 106
 107         if (isl_schedule_node_get_type(node) != isl_schedule_node_sequence)
 108                 return isl_schedule_node_child(node, 0);
 109
 110         n = isl_schedule_node_n_children(node);
 111         for (i = 0; i < n; ++i) {
 112                 int is_core;
 113
 114                 node = isl_schedule_node_child(node, i);
 115                 is_core = node_is_core(node, core);
 116
 117                 if (is_core < 0)
 118                         return isl_schedule_node_free(node);
 119                 if (is_core)
 120                         return isl_schedule_node_child(node, 0);
 121
 122                 node = isl_schedule_node_parent(node);
 123         }
 124
 125         isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,
 126                 "core child not found", return isl_schedule_node_free(node));
 127 }
 128
 129 /* Move down the branch between "kernel" and "thread" until
 130  * the "thread" mark is reached, where the branch containing the "thread"
 131  * mark is identified by the domain elements in "core".
 132  */
 133 __isl_give isl_schedule_node *gpu_tree_move_down_to_thread(
 134         __isl_take isl_schedule_node *node, __isl_keep isl_union_set *core)
 135 {
 136         int is_thread;
 137
 138         while ((is_thread = node_is_thread(node)) == 0)
 139                 node = core_child(node, core);
 140         if (is_thread < 0)
 141                 node = isl_schedule_node_free(node);
 142
 143         return node;
 144 }
 145
 146 /* Move up the tree underneath the "thread" mark until
 147  * the "thread" mark is reached.
 148  */
 149 __isl_give isl_schedule_node *gpu_tree_move_up_to_thread(
 150         __isl_take isl_schedule_node *node)
 151 {
 152         int is_thread;
 153
 154         while ((is_thread = node_is_thread(node)) == 0)
 155                 node = isl_schedule_node_parent(node);
 156         if (is_thread < 0)
 157                 node = isl_schedule_node_free(node);
 158
 159         return node;
 160 }
 161
 162 /* Move up the tree underneath the "kernel" mark until
 163  * the "kernel" mark is reached.
 164  */
 165 __isl_give isl_schedule_node *gpu_tree_move_up_to_kernel(
 166         __isl_take isl_schedule_node *node)
 167 {
 168         int is_kernel;
 169
 170         while ((is_kernel = gpu_tree_node_is_kernel(node)) == 0)
 171                 node = isl_schedule_node_parent(node);
 172         if (is_kernel < 0)
 173                 node = isl_schedule_node_free(node);
 174
 175         return node;
 176 }
 177
 178 /* Move down from the "kernel" mark (or at least a node with schedule
 179  * depth smaller than or equal to "depth") to a band node at schedule
 180  * depth "depth".  The "thread" mark is assumed to have a schedule
 181  * depth greater than or equal to "depth".  The branch containing the
 182  * "thread" mark is identified by the domain elements in "core".
 183  *
 184  * If the desired schedule depth is in the middle of band node,
 185  * then the band node is split into two pieces, the second piece
 186  * at the desired schedule depth.
 187  */
 188 __isl_give isl_schedule_node *gpu_tree_move_down_to_depth(
 189         __isl_take isl_schedule_node *node, int depth,
 190         __isl_keep isl_union_set *core)
 191 {
 192         int is_thread;
 193
 194         while (node && isl_schedule_node_get_schedule_depth(node) < depth) {
 195                 if (isl_schedule_node_get_type(node) ==
 196                                                     isl_schedule_node_band) {
 197                         int node_depth, node_dim;
 198                         node_depth = isl_schedule_node_get_schedule_depth(node);
 199                         node_dim = isl_schedule_node_band_n_member(node);
 200                         if (node_depth + node_dim > depth)
 201                                 node = isl_schedule_node_band_split(node,
 202                                                         depth - node_depth);
 203                 }
 204                 node = core_child(node, core);
 205         }
 206         while ((is_thread = node_is_thread(node)) == 0 &&
 207             isl_schedule_node_get_type(node) != isl_schedule_node_band)
 208                 node = core_child(node, core);
 209         if (is_thread < 0)
 210                 node = isl_schedule_node_free(node);
 211
 212         return node;
 213 }
 214
 215 /* Create a union set containing a single set with a tuple identifier
 216  * called "syncX" and user pointer equal to "kernel".
 217  */
 218 static __isl_give isl_union_set *create_sync_domain(struct ppcg_kernel *kernel)
 219 {
 220         isl_space *space;
 221         isl_id *id;
 222         char name[40];
 223
 224         space = isl_space_set_alloc(kernel->ctx, 0, 0);
 225         snprintf(name, sizeof(name), "sync%d", kernel->n_sync++);
 226         id = isl_id_alloc(kernel->ctx, name, kernel);
 227         space = isl_space_set_tuple_id(space, isl_dim_set, id);
 228         return isl_union_set_from_set(isl_set_universe(space));
 229 }
 230
 231 /* Is "id" the identifier of a synchronization statement inside "kernel"?
 232  * That is, does its name start with "sync" and does it point to "kernel"?
 233  */
 234 int gpu_tree_id_is_sync(__isl_keep isl_id *id, struct ppcg_kernel *kernel)
 235 {
 236         const char *name;
 237
 238         name = isl_id_get_name(id);
 239         if (!name)
 240                 return 0;
 241         else if (strncmp(name, "sync", 4))
 242                 return 0;
 243         return isl_id_get_user(id) == kernel;
 244 }
 245
 246 /* Does "domain" consist of a single set with a tuple identifier
 247  * corresponding to a synchronization for "kernel"?
 248  */
 249 static int domain_is_sync(__isl_keep isl_union_set *domain,
 250         struct ppcg_kernel *kernel)
 251 {
 252         int is_sync;
 253         isl_id *id;
 254         isl_set *set;
 255
 256         if (isl_union_set_n_set(domain) != 1)
 257                 return 0;
 258         set = isl_set_from_union_set(isl_union_set_copy(domain));
 259         id = isl_set_get_tuple_id(set);
 260         is_sync = gpu_tree_id_is_sync(id, kernel);
 261         isl_id_free(id);
 262         isl_set_free(set);
 263
 264         return is_sync;
 265 }
 266
 267 /* Does "node" point to a filter selecting a synchronization statement
 268  * for "kernel"?
 269  */
 270 static int node_is_sync_filter(__isl_keep isl_schedule_node *node,
 271         struct ppcg_kernel *kernel)
 272 {
 273         int is_sync;
 274         enum isl_schedule_node_type type;
 275         isl_union_set *domain;
 276
 277         if (!node)
 278                 return -1;
 279         type = isl_schedule_node_get_type(node);
 280         if (type != isl_schedule_node_filter)
 281                 return 0;
 282         domain = isl_schedule_node_filter_get_filter(node);
 283         is_sync = domain_is_sync(domain, kernel);
 284         isl_union_set_free(domain);
 285
 286         return is_sync;
 287 }
 288
 289 /* Is "node" part of a sequence with a previous synchronization statement
 290  * for "kernel"?
 291  * That is, is the parent of "node" a filter such that there is
 292  * a previous filter that picks out exactly such a synchronization statement?
 293  */
 294 static int has_preceding_sync(__isl_keep isl_schedule_node *node,
 295         struct ppcg_kernel *kernel)
 296 {
 297         int found = 0;
 298
 299         node = isl_schedule_node_copy(node);
 300         node = isl_schedule_node_parent(node);
 301         while (!found && isl_schedule_node_has_previous_sibling(node)) {
 302                 node = isl_schedule_node_previous_sibling(node);
 303                 if (!node)
 304                         break;
 305                 found = node_is_sync_filter(node, kernel);
 306         }
 307         if (!node)
 308                 found = -1;
 309         isl_schedule_node_free(node);
 310
 311         return found;
 312 }
 313
 314 /* Is "node" part of a sequence with a subsequent synchronization statement
 315  * for "kernel"?
 316  * That is, is the parent of "node" a filter such that there is
 317  * a subsequent filter that picks out exactly such a synchronization statement?
 318  */
 319 static int has_following_sync(__isl_keep isl_schedule_node *node,
 320         struct ppcg_kernel *kernel)
 321 {
 322         int found = 0;
 323
 324         node = isl_schedule_node_copy(node);
 325         node = isl_schedule_node_parent(node);
 326         while (!found && isl_schedule_node_has_next_sibling(node)) {
 327                 node = isl_schedule_node_next_sibling(node);
 328                 if (!node)
 329                         break;
 330                 found = node_is_sync_filter(node, kernel);
 331         }
 332         if (!node)
 333                 found = -1;
 334         isl_schedule_node_free(node);
 335
 336         return found;
 337 }
 338
 339 /* Does the subtree rooted at "node" (which is a band node) contain
 340  * any synchronization statement for "kernel" that precedes
 341  * the core computation of "kernel" (identified by the elements
 342  * in kernel->core)?
 343  */
 344 static int has_sync_before_core(__isl_keep isl_schedule_node *node,
 345         struct ppcg_kernel *kernel)
 346 {
 347         int has_sync = 0;
 348         int is_thread;
 349
 350         node = isl_schedule_node_copy(node);
 351         while ((is_thread = node_is_thread(node)) == 0) {
 352                 node = core_child(node, kernel->core);
 353                 has_sync = has_preceding_sync(node, kernel);
 354                 if (has_sync < 0 || has_sync)
 355                         break;
 356         }
 357         if (is_thread < 0 || !node)
 358                 has_sync = -1;
 359         isl_schedule_node_free(node);
 360
 361         return has_sync;
 362 }
 363
 364 /* Does the subtree rooted at "node" (which is a band node) contain
 365  * any synchronization statement for "kernel" that follows
 366  * the core computation of "kernel" (identified by the elements
 367  * in kernel->core)?
 368  */
 369 static int has_sync_after_core(__isl_keep isl_schedule_node *node,
 370         struct ppcg_kernel *kernel)
 371 {
 372         int has_sync = 0;
 373         int is_thread;
 374
 375         node = isl_schedule_node_copy(node);
 376         while ((is_thread = node_is_thread(node)) == 0) {
 377                 node = core_child(node, kernel->core);
 378                 has_sync = has_following_sync(node, kernel);
 379                 if (has_sync < 0 || has_sync)
 380                         break;
 381         }
 382         if (is_thread < 0 || !node)
 383                 has_sync = -1;
 384         isl_schedule_node_free(node);
 385
 386         return has_sync;
 387 }
 388
 389 /* Insert (or extend) an extension on top of "node" that puts
 390  * a synchronization node for "kernel" before "node".
 391  * Return a pointer to the original node in the updated schedule tree.
 392  */
 393 static __isl_give isl_schedule_node *insert_sync_before(
 394         __isl_take isl_schedule_node *node, struct ppcg_kernel *kernel)
 395 {
 396         isl_union_set *domain;
 397         isl_schedule_node *graft;
 398
 399         if (!node)
 400                 return NULL;
 401
 402         domain = create_sync_domain(kernel);
 403         graft = isl_schedule_node_from_domain(domain);
 404         node = isl_schedule_node_graft_before(node, graft);
 405
 406         return node;
 407 }
 408
 409 /* Insert (or extend) an extension on top of "node" that puts
 410  * a synchronization node for "kernel" afater "node".
 411  * Return a pointer to the original node in the updated schedule tree.
 412  */
 413 static __isl_give isl_schedule_node *insert_sync_after(
 414         __isl_take isl_schedule_node *node, struct ppcg_kernel *kernel)
 415 {
 416         isl_union_set *domain;
 417         isl_schedule_node *graft;
 418
 419         if (!node)
 420                 return NULL;
 421
 422         domain = create_sync_domain(kernel);
 423         graft = isl_schedule_node_from_domain(domain);
 424         node = isl_schedule_node_graft_after(node, graft);
 425
 426         return node;
 427 }
 428
 429 /* Insert an extension on top of "node" that puts a synchronization node
 430  * for "kernel" before "node" unless there already is
 431  * such a synchronization node.
 432  */
 433 __isl_give isl_schedule_node *gpu_tree_ensure_preceding_sync(
 434         __isl_take isl_schedule_node *node, struct ppcg_kernel *kernel)
 435 {
 436         int has_sync;
 437
 438         has_sync = has_preceding_sync(node, kernel);
 439         if (has_sync < 0)
 440                 return isl_schedule_node_free(node);
 441         if (has_sync)
 442                 return node;
 443         return insert_sync_before(node, kernel);
 444 }
 445
 446 /* Insert an extension on top of "node" that puts a synchronization node
 447  * for "kernel" after "node" unless there already is
 448  * such a synchronization node.
 449  */
 450 __isl_give isl_schedule_node *gpu_tree_ensure_following_sync(
 451         __isl_take isl_schedule_node *node, struct ppcg_kernel *kernel)
 452 {
 453         int has_sync;
 454
 455         has_sync = has_following_sync(node, kernel);
 456         if (has_sync < 0)
 457                 return isl_schedule_node_free(node);
 458         if (has_sync)
 459                 return node;
 460         return insert_sync_after(node, kernel);
 461 }
 462
 463 /* Insert an extension on top of "node" that puts a synchronization node
 464  * for "kernel" after "node" unless there already is such a sync node or
 465  * "node" itself already * contains a synchronization node following
 466  * the core computation of "kernel".
 467  */
 468 __isl_give isl_schedule_node *gpu_tree_ensure_sync_after_core(
 469         __isl_take isl_schedule_node *node, struct ppcg_kernel *kernel)
 470 {
 471         int has_sync;
 472
 473         has_sync = has_sync_after_core(node, kernel);
 474         if (has_sync < 0)
 475                 return isl_schedule_node_free(node);
 476         if (has_sync)
 477                 return node;
 478         has_sync = has_following_sync(node, kernel);
 479         if (has_sync < 0)
 480                 return isl_schedule_node_free(node);
 481         if (has_sync)
 482                 return node;
 483         return insert_sync_after(node, kernel);
 484 }
 485
 486 /* Move left in the sequence on top of "node" to a synchronization node
 487  * for "kernel".
 488  * If "node" itself contains a synchronization node preceding
 489  * the core computation of "kernel", then return "node" itself.
 490  * Otherwise, if "node" does not have a preceding synchronization node,
 491  * then create one first.
 492  */
 493 __isl_give isl_schedule_node *gpu_tree_move_left_to_sync(
 494         __isl_take isl_schedule_node *node, struct ppcg_kernel *kernel)
 495 {
 496         int has_sync;
 497         int is_sync;
 498
 499         has_sync = has_sync_before_core(node, kernel);
 500         if (has_sync < 0)
 501                 return isl_schedule_node_free(node);
 502         if (has_sync)
 503                 return node;
 504         node = gpu_tree_ensure_preceding_sync(node, kernel);
 505         node = isl_schedule_node_parent(node);
 506         while ((is_sync = node_is_sync_filter(node, kernel)) == 0)
 507                 node = isl_schedule_node_previous_sibling(node);
 508         if (is_sync < 0)
 509                 node = isl_schedule_node_free(node);
 510         node = isl_schedule_node_child(node, 0);
 511
 512         return node;
 513 }
 514
 515 /* Move right in the sequence on top of "node" to a synchronization node
 516  * for "kernel".
 517  * If "node" itself contains a synchronization node following
 518  * the core computation of "kernel", then return "node" itself.
 519  * Otherwise, if "node" does not have a following synchronization node,
 520  * then create one first.
 521  */
 522 __isl_give isl_schedule_node *gpu_tree_move_right_to_sync(
 523         __isl_take isl_schedule_node *node, struct ppcg_kernel *kernel)
 524 {
 525         int has_sync;
 526         int is_sync;
 527
 528         has_sync = has_sync_after_core(node, kernel);
 529         if (has_sync < 0)
 530                 return isl_schedule_node_free(node);
 531         if (has_sync)
 532                 return node;
 533         node = gpu_tree_ensure_following_sync(node, kernel);
 534         node = isl_schedule_node_parent(node);
 535         while ((is_sync = node_is_sync_filter(node, kernel)) == 0)
 536                 node = isl_schedule_node_next_sibling(node);
 537         if (is_sync < 0)
 538                 node = isl_schedule_node_free(node);
 539         node = isl_schedule_node_child(node, 0);
 540
 541         return node;
 542 }