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/union_set.h>
  13
  14 #include "gpu_tree.h"
  15
  16 /* The functions in this file are used to navigate part of a schedule tree
  17  * that is mapped to blocks.  Initially, this part consists of a linear
  18  * branch segment with a mark node with name "kernel" on the outer end
  19  * and a mark node with name "thread" on the inner end.
  20  * During the mapping to blocks, branching may be introduced, but only
  21  * one of the elements in each sequence contains the "thread" mark.
  22  * The filter of this element (and only this filter) contains
  23  * domain elements identified by the "core" argument of the functions
  24  * that move down this tree.
  25  */
  26
  27 /* Is "node" a mark node with an identifier called "name"?
  28  */
  29 static int is_marked(__isl_keep isl_schedule_node *node, const char *name)
  30 {
  31         isl_id *mark;
  32         int has_name;
  33
  34         if (!node)
  35                 return -1;
  36
  37         if (isl_schedule_node_get_type(node) != isl_schedule_node_mark)
  38                 return 0;
  39
  40         mark = isl_schedule_node_mark_get_id(node);
  41         if (!mark)
  42                 return -1;
  43
  44         has_name = !strcmp(isl_id_get_name(mark), name);
  45         isl_id_free(mark);
  46
  47         return has_name;
  48 }
  49
  50 /* Is "node" a mark node with an identifier called "kernel"?
  51  */
  52 int gpu_tree_node_is_kernel(__isl_keep isl_schedule_node *node)
  53 {
  54         return is_marked(node, "kernel");
  55 }
  56
  57 /* Is "node" a mark node with an identifier called "thread"?
  58  */
  59 static int node_is_thread(__isl_keep isl_schedule_node *node)
  60 {
  61         return is_marked(node, "thread");
  62 }
  63
  64 /* Assuming "node" is a filter node, does it correspond to the branch
  65  * that contains the "thread" mark, i.e., does it contain any elements
  66  * in "core"?
  67  */
  68 static int node_is_core(__isl_keep isl_schedule_node *node,
  69         __isl_keep isl_union_set *core)
  70 {
  71         int disjoint;
  72         isl_union_set *filter;
  73
  74         filter = isl_schedule_node_filter_get_filter(node);
  75         disjoint = isl_union_set_is_disjoint(filter, core);
  76         isl_union_set_free(filter);
  77         if (disjoint < 0)
  78                 return -1;
  79
  80         return !disjoint;
  81 }
  82
  83 /* Move to the only child of "node" that has the "thread" mark as descendant,
  84  * where the branch containing this mark is identified by the domain elements
  85  * in "core".
  86  *
  87  * If "node" is not a sequence, then it only has one child and we move
  88  * to that single child.
  89  * Otherwise, we check each of the filters in the children, pick
  90  * the one that corresponds to "core" and return a pointer to the child
  91  * of the filter node.
  92  */
  93 static __isl_give isl_schedule_node *core_child(
  94         __isl_take isl_schedule_node *node, __isl_keep isl_union_set *core)
  95 {
  96         int i, n;
  97
  98         if (isl_schedule_node_get_type(node) != isl_schedule_node_sequence)
  99                 return isl_schedule_node_child(node, 0);
 100
 101         n = isl_schedule_node_n_children(node);
 102         for (i = 0; i < n; ++i) {
 103                 int is_core;
 104
 105                 node = isl_schedule_node_child(node, i);
 106                 is_core = node_is_core(node, core);
 107
 108                 if (is_core < 0)
 109                         return isl_schedule_node_free(node);
 110                 if (is_core)
 111                         return isl_schedule_node_child(node, 0);
 112
 113                 node = isl_schedule_node_parent(node);
 114         }
 115
 116         isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,
 117                 "core child not found", return isl_schedule_node_free(node));
 118 }
 119
 120 /* Move down the branch between "kernel" and "thread" until
 121  * the "thread" mark is reached, where the branch containing the "thread"
 122  * mark is identified by the domain elements in "core".
 123  */
 124 __isl_give isl_schedule_node *gpu_tree_move_down_to_thread(
 125         __isl_take isl_schedule_node *node, __isl_keep isl_union_set *core)
 126 {
 127         int is_thread;
 128
 129         while ((is_thread = node_is_thread(node)) == 0)
 130                 node = core_child(node, core);
 131         if (is_thread < 0)
 132                 node = isl_schedule_node_free(node);
 133
 134         return node;
 135 }
 136
 137 /* Move up the tree underneath the "thread" mark until
 138  * the "thread" mark is reached.
 139  */
 140 __isl_give isl_schedule_node *gpu_tree_move_up_to_thread(
 141         __isl_take isl_schedule_node *node)
 142 {
 143         int is_thread;
 144
 145         while ((is_thread = node_is_thread(node)) == 0)
 146                 node = isl_schedule_node_parent(node);
 147         if (is_thread < 0)
 148                 node = isl_schedule_node_free(node);
 149
 150         return node;
 151 }
 152
 153 /* Move up the tree underneath the "kernel" mark until
 154  * the "kernel" mark is reached.
 155  */
 156 __isl_give isl_schedule_node *gpu_tree_move_up_to_kernel(
 157         __isl_take isl_schedule_node *node)
 158 {
 159         int is_kernel;
 160
 161         while ((is_kernel = gpu_tree_node_is_kernel(node)) == 0)
 162                 node = isl_schedule_node_parent(node);
 163         if (is_kernel < 0)
 164                 node = isl_schedule_node_free(node);
 165
 166         return node;
 167 }
 168
 169 /* Move down from the "kernel" mark (or at least a node with schedule
 170  * depth smaller than or equal to "depth") to a band node at schedule
 171  * depth "depth".  The "thread" mark is assumed to have a schedule
 172  * depth greater than or equal to "depth".  The branch containing the
 173  * "thread" mark is identified by the domain elements in "core".
 174  *
 175  * If the desired schedule depth is in the middle of band node,
 176  * then the band node is split into two pieces, the second piece
 177  * at the desired schedule depth.
 178  */
 179 __isl_give isl_schedule_node *gpu_tree_move_down_to_depth(
 180         __isl_take isl_schedule_node *node, int depth,
 181         __isl_keep isl_union_set *core)
 182 {
 183         int is_thread;
 184
 185         while (node && isl_schedule_node_get_schedule_depth(node) < depth) {
 186                 if (isl_schedule_node_get_type(node) ==
 187                                                     isl_schedule_node_band) {
 188                         int node_depth, node_dim;
 189                         node_depth = isl_schedule_node_get_schedule_depth(node);
 190                         node_dim = isl_schedule_node_band_n_member(node);
 191                         if (node_depth + node_dim > depth)
 192                                 node = isl_schedule_node_band_split(node,
 193                                                         depth - node_depth);
 194                 }
 195                 node = core_child(node, core);
 196         }
 197         while ((is_thread = node_is_thread(node)) == 0 &&
 198             isl_schedule_node_get_type(node) != isl_schedule_node_band)
 199                 node = core_child(node, core);
 200         if (is_thread < 0)
 201                 node = isl_schedule_node_free(node);
 202
 203         return node;
 204 }