include/isa/adg.h

   1 #ifndef ISA_ADG_H
   2 #define ISA_ADG_H
   3
   4 #include <stdio.h>
   5 #include <vector>
   6 #include <yaml.h>
   7 #include <isl/id.h>
   8 #include <isl/val.h>
   9 #include <isl/aff.h>
  10 #include <isl/set.h>
  11 #include <isl/map.h>
  12
  13 /* Represents a (possibly indexed) variable of a certain type.
  14  *
  15  * "expr" contains a pointer to an allocated buffer created by get_expr().
  16  */
  17 struct adg_var {
  18         isl_pw_multi_aff *access;
  19         isl_id *type;
  20
  21         adg_var() : access(NULL), type(NULL), expr(NULL) {}
  22         adg_var(const adg_var &var) : expr(NULL) {
  23                 access = isl_pw_multi_aff_copy(var.access);
  24                 type = isl_id_copy(var.type);
  25         }
  26         ~adg_var() {
  27                 isl_pw_multi_aff_free(access);
  28                 isl_id_free(type);
  29                 free(expr);
  30         }
  31
  32         __isl_keep const char *get_expr();
  33         void print(FILE *out = stdout);
  34         int print(yaml_emitter_t *emitter);
  35         int is_equal(adg_var *var2);
  36 private:
  37         char *expr;
  38 };
  39
  40 /* Represents a named piecewise affine expression.
  41  */
  42 struct adg_expr {
  43         isl_id *name;
  44         isl_pw_aff *expr;
  45
  46         adg_expr() : name(NULL), expr(NULL) {}
  47         adg_expr(const adg_expr &copy) {
  48                 name = isl_id_copy(copy.name);
  49                 expr = isl_pw_aff_copy(copy.expr);
  50         }
  51         ~adg_expr() {
  52                 isl_id_free(name);
  53                 isl_pw_aff_free(expr);
  54         }
  55
  56         int print(yaml_emitter_t *emitter);
  57         int is_equal(adg_expr *expr2);
  58 };
  59
  60 /* Represents a domain.  The set "bounds" should have no existentially
  61  * quantified variables.  Instead, the domain may be nested (possibly
  62  * multiple times) with extra control variables in the "local" output
  63  * of the nested map.  Each of these extra variables is represented
  64  * by an adg_expr in the controls vector.
  65  * Additionally, the domain may also be nested with extra filter
  66  * variables in the input of the nested map.  Each of these filters
  67  * is represented by an adg_var in the filters vector.
  68  * The different types of nestings may be interleaved.
  69  */
  70 struct adg_domain {
  71         isl_set *bounds;
  72         std::vector<adg_expr *> controls;
  73         std::vector<adg_var *> filters;
  74
  75         adg_domain() : bounds(NULL) {}
  76         adg_domain(__isl_take isl_set *bounds) : bounds(bounds) {}
  77         ~adg_domain() {
  78                 for (int i = 0; i < controls.size(); ++i)
  79                         delete controls[i];
  80                 for (int i = 0; i < filters.size(); ++i)
  81                         delete filters[i];
  82                 isl_set_free(bounds);
  83         }
  84
  85         int print(yaml_emitter_t *emitter);
  86         int is_equal(adg_domain *domain2);
  87 };
  88
  89 /* Represents a port with a name, belonging to a node called node_name
  90  * and connected to an edge called edge_name.
  91  * For each iteration in "domain" each of adg_vars in "vars"
  92  * is either read from the edge or written to the edge.
  93  *
  94  * edge_nr is the number of the (non-control) edge to which
  95  *      port is connected or related.
  96  * arg_pos reflects the argument position of the variable accessed
  97  *      in this port.
  98  */
  99 struct adg_port {
 100         isl_id *name;
 101         isl_id *node_name;
 102         isl_id *edge_name;
 103         std::vector<adg_var *> vars;
 104         adg_domain *domain;
 105         int edge_nr;
 106         int arg_pos;
 107
 108         adg_port() : name(NULL), node_name(NULL), edge_name(NULL),
 109                 domain(NULL), edge_nr(-1), arg_pos(-1) {}
 110         ~adg_port() {
 111                 isl_id_free(name);
 112                 isl_id_free(node_name);
 113                 isl_id_free(edge_name);
 114                 for (int i = 0; i < vars.size(); ++i)
 115                         delete vars[i];
 116                 delete domain;
 117         }
 118
 119         int print(yaml_emitter_t *emitter);
 120         int is_equal(adg_port *port2);
 121 };
 122
 123 /* Represents a gate called "name", belonging to a node calles "node_name"
 124  * that copies the value of "in" to "out" for each iteration in "domain".
 125  */
 126 struct adg_gate {
 127         isl_id *name;
 128         isl_id *node_name;
 129         adg_var *in;
 130         adg_var *out;
 131         adg_domain *domain;
 132
 133         adg_gate() : name(NULL), node_name(NULL),
 134                 in(NULL), out(NULL), domain(NULL) {}
 135         ~adg_gate() {
 136                 isl_id_free(name);
 137                 isl_id_free(node_name);
 138                 delete in;
 139                 delete out;
 140                 delete domain;
 141         }
 142
 143         int print(yaml_emitter_t *emitter);
 144         int is_equal(adg_gate *gate2);
 145 };
 146
 147 enum adg_arg_type {
 148         adg_arg_value,
 149         adg_arg_reference,
 150         adg_arg_return,
 151         adg_arg_unknown
 152 };
 153
 154 /* Represents an argument to a function.
 155  * It contains the variable that is read or written and the way
 156  * it is passed to/from the function.
 157  */
 158 struct adg_arg {
 159         adg_var *var;
 160         enum adg_arg_type type;
 161
 162         adg_arg() : var(NULL), type(adg_arg_unknown) {}
 163         ~adg_arg() {
 164                 delete var;
 165         }
 166
 167         int print(yaml_emitter_t *emitter);
 168         int is_equal(adg_arg *arg2);
 169 };
 170
 171 /* Represents the execution of a function called "name" for each
 172  * iteration of "domain".
 173  * The "ctrl" vector contains references to variables that should
 174  * be written on each iteration of the function.  The value that
 175  * should be written is given by the expr field of the adg_expr.
 176  */
 177 struct adg_function {
 178         isl_id *name;
 179         adg_domain *domain;
 180
 181         std::vector<adg_arg *> in;
 182         std::vector<adg_arg *> out;
 183         std::vector<adg_expr *> ctrl;
 184
 185         adg_function() : name(NULL), domain(NULL) {}
 186         ~adg_function() {
 187                 isl_id_free(name);
 188                 delete domain;
 189                 for (int i = 0; i < in.size(); ++i)
 190                         delete in[i];
 191                 for (int i = 0; i < out.size(); ++i)
 192                         delete out[i];
 193                 for (int i = 0; i < ctrl.size(); ++i)
 194                         delete ctrl[i];
 195         }
 196
 197         int print(yaml_emitter_t *emitter);
 198         int is_equal(adg_function *function2);
 199 };
 200
 201 enum adg_edge_type {
 202         adg_edge_fifo,
 203         adg_edge_sticky_fifo,
 204         adg_edge_shift_register,
 205         adg_edge_broadcast,
 206         adg_edge_generic,
 207         adg_edge_error
 208 };
 209
 210 /* Represents an edge called "name" connecting the port "from_port_name"
 211  * in node "from_node_name" to the port "to_port_name" in node "to_node_name".
 212  *
 213  * "map" maps an iteration of the "to_port_name" to the corresponding
 214  * iteration of the "from_port_name", i.e., to the iteration that wrote
 215  * the values that is being read in the given iteration.
 216  *
 217  * If each parameter is assigned its "val" values, then a buffer size
 218  * of "value_size" on this edge is sufficient to allow for a deadlock
 219  * free execution.
 220  */
 221 struct adg_edge {
 222         isl_id *name;
 223         isl_id *from_node_name;
 224         isl_id *from_port_name;
 225         isl_id *to_node_name;
 226         isl_id *to_port_name;
 227
 228         enum adg_edge_type type;
 229
 230         isl_multi_aff *map;
 231         isl_val *value_size;
 232
 233         adg_edge() : name(NULL), from_node_name(NULL), from_port_name(NULL),
 234                     to_node_name(NULL), to_port_name(NULL), map(NULL),
 235                     value_size(NULL), type(adg_edge_fifo) { }
 236         ~adg_edge() {
 237                 isl_id_free(name);
 238                 isl_id_free(from_node_name);
 239                 isl_id_free(from_port_name);
 240                 isl_id_free(to_node_name);
 241                 isl_id_free(to_port_name);
 242                 isl_multi_aff_free(map);
 243                 isl_val_free(value_size);
 244         }
 245
 246         int print(yaml_emitter_t *emitter);
 247         int is_equal(adg_edge *edge2);
 248 };
 249
 250 /* Represents a node called "name" with input ports, gates, expressions,
 251  * output ports and function.
 252  *
 253  * "domain" is the iteration domain.
 254  * "schedule" is the schedule for this node.
 255  * "lifting" is a mapping that has been used to remove
 256  * existentially quantified from the domain of this node and that
 257  * should be applied to the domains of the subelements to ensure
 258  * that they have the same initial (static) control variables.
 259  */
 260 struct adg_node {
 261         isl_id *name;
 262
 263         std::vector<adg_port *> input_ports;
 264         std::vector<adg_gate *> gates;
 265         std::vector<adg_expr *> expressions;
 266         std::vector<adg_port *> output_ports;
 267
 268         adg_function *function;
 269
 270         adg_domain *domain;
 271         isl_map *schedule;
 272         isl_basic_map *lifting;
 273
 274         adg_node() : name(NULL), function(NULL), domain(NULL), schedule(NULL),
 275                 lifting(NULL) {}
 276         ~adg_node() {
 277                 isl_id_free(name);
 278                 for (int i = 0; i < input_ports.size(); ++i)
 279                         delete input_ports[i];
 280                 for (int i = 0; i < gates.size(); ++i)
 281                         delete gates[i];
 282                 for (int i = 0; i < expressions.size(); ++i)
 283                         delete expressions[i];
 284                 for (int i = 0; i < output_ports.size(); ++i)
 285                         delete output_ports[i];
 286                 if (function)
 287                         delete function;
 288                 isl_map_free(schedule);
 289                 isl_basic_map_free(lifting);
 290                 delete domain;
 291         }
 292         int print(yaml_emitter_t *emitter);
 293         int is_equal(adg_node *node2);
 294 };
 295
 296 /* Represents a parameters called "name" with lower bound "lb", upper
 297  * bound "ub" and default value "val".
 298  */
 299 struct adg_param {
 300         isl_id *name;
 301         isl_aff *lb;
 302         isl_aff *ub;
 303         isl_aff *val;
 304
 305         adg_param() : name(NULL), lb(NULL), ub(NULL), val(NULL) {}
 306         ~adg_param() {
 307                 isl_id_free(name);
 308                 isl_aff_free(lb);
 309                 isl_aff_free(ub);
 310                 isl_aff_free(val);
 311         }
 312
 313         int print(yaml_emitter_t *emitter);
 314         int is_equal(adg_param *param2);
 315 };
 316
 317 /* Represents an approximate dependence graph called "name", with parameters,
 318  * nodes and edges.
 319  *
 320  * "context" represents the constraints on the parameters.
 321  * "iterators" represents the iterators used in the domains of the adg.
 322  * "all_iterators" represents the iterators used in the schedules of the adg.
 323  * "iterator_map" maps (some) elements of "all_iterators" to the
 324  * corresponding element in "iterators".
 325  * "controls" collects all static control variables so that we can
 326  *      reuse them in to_control.
 327  */
 328 struct adg {
 329         isl_id *name;
 330         isl_set *context;
 331         isl_map *iterator_map;
 332
 333         std::vector<adg_param *> params;
 334         std::vector<adg_node *> nodes;
 335         std::vector<adg_edge *> edges;
 336         std::vector<isl_id *> iterators;
 337         std::vector<isl_id *> all_iterators;
 338         std::vector<adg_expr *> controls;
 339
 340         adg() : name(NULL), context(NULL), iterator_map(NULL) {}
 341         ~adg() {
 342                 isl_id_free(name);
 343                 isl_set_free(context);
 344                 isl_map_free(iterator_map);
 345                 for (int i = 0; i < params.size(); ++i)
 346                         delete params[i];
 347                 for (int i = 0; i < nodes.size(); ++i)
 348                         delete nodes[i];
 349                 for (int i = 0; i < edges.size(); ++i)
 350                         delete edges[i];
 351                 for (int i = 0; i < all_iterators.size(); ++i)
 352                         isl_id_free(all_iterators[i]);
 353                 for (int i = 0; i < iterators.size(); ++i)
 354                         isl_id_free(iterators[i]);
 355                 for (int i = 0; i < controls.size(); ++i)
 356                         delete controls[i];
 357         }
 358         adg_node *node_by_id(__isl_keep isl_id *id);
 359         void print(FILE *out = stdout);
 360         int print(yaml_emitter_t *emitter);
 361         int is_equal(adg *adg2);
 362         adg_expr *to_control(__isl_take isl_aff *expr);
 363 };
 364
 365 #endif