adg_xml.cc

   1 /*
   2  * Copyright 2011 Leiden University. All rights reserved.
   3  */
   4
   5 #include <assert.h>
   6 #include <sstream>
   7 #include <libxml/xmlwriter.h>
   8 #include <isl/mat.h>
   9 #include <isl/id.h>
  10 #include <isl/space.h>
  11 #include <isl/val.h>
  12 #include <isl/aff.h>
  13 #include <isl/set.h>
  14 #include <isl/map.h>
  15 #include <isl/ast_build.h>
  16 #include <isl/union_map.h>
  17 #include "adg_xml.h"
  18 #include "xml_AST.h"
  19
  20 static void writeVar(xmlTextWriterPtr writer, adg_var *var)
  21 {
  22         int rc;
  23
  24         assert(var->access);
  25         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
  26                                         BAD_CAST var->get_expr());
  27         assert(rc >= 0);
  28
  29         assert(var->type);
  30         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "dataType",
  31                                         BAD_CAST isl_id_get_name(var->type));
  32         assert(rc >= 0);
  33 }
  34
  35 static void writeVar(xmlTextWriterPtr writer, const char *type, adg_var *var)
  36 {
  37         int rc;
  38
  39         rc = xmlTextWriterStartElement(writer, BAD_CAST type);
  40         assert(rc >= 0);
  41
  42         writeVar(writer, var);
  43
  44         rc = xmlTextWriterEndElement(writer);
  45         assert(rc >= 0);
  46 }
  47
  48 static void writeArg(xmlTextWriterPtr writer, const char *type, adg_arg *arg)
  49 {
  50         int rc;
  51
  52         rc = xmlTextWriterStartElement(writer, BAD_CAST type);
  53         assert(rc >= 0);
  54
  55         writeVar(writer, arg->var);
  56
  57         switch (arg->type) {
  58         case adg_arg_value:
  59                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "pass",
  60                                                  BAD_CAST "value");
  61                 break;
  62         case adg_arg_return:
  63                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "pass",
  64                                                  BAD_CAST "return_value");
  65                 break;
  66         case adg_arg_reference:
  67                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "pass",
  68                                                  BAD_CAST "reference");
  69                 break;
  70         case adg_arg_unknown:
  71                 assert(0);
  72                 break;
  73         }
  74         assert(rc >= 0);
  75
  76         rc = xmlTextWriterEndElement(writer);
  77         assert(rc >= 0);
  78 }
  79
  80 /* Print "v * name" onto os.
  81  */
  82 static void print_term(std::ostringstream &os, __isl_keep isl_val *v,
  83         const char *name)
  84 {
  85         if (!isl_val_is_one(v)) {
  86                 os << isl_val_get_num_si(v);
  87                 os << "*";
  88         }
  89         os << name;
  90 }
  91
  92 static void print_aff_expr(std::ostringstream &os, __isl_keep isl_aff *aff);
  93
  94 /* Print "v * div(aff)" onto os.
  95  */
  96 static void print_term(std::ostringstream &os, __isl_keep isl_val *v,
  97         __isl_take isl_aff *aff)
  98 {
  99         isl_val *d;
 100
 101         if (!isl_val_is_one(v)) {
 102                 os << isl_val_get_num_si(v);
 103                 os << "*";
 104         }
 105         d = isl_aff_get_denominator_val(aff);
 106         aff = isl_aff_scale_val(aff, isl_val_copy(d));
 107         os << "div(";
 108         print_aff_expr(os, aff);
 109         os << ",";
 110         os << isl_val_get_num_si(d);
 111         os << ")";
 112         isl_val_free(d);
 113         isl_aff_free(aff);
 114 }
 115
 116 /* Print "aff" onto os.
 117  */
 118 static void print_aff_expr(std::ostringstream &os, __isl_keep isl_aff *aff)
 119 {
 120         bool first = true;
 121         isl_val *v, *d;
 122         enum isl_dim_type types[] = { isl_dim_in, isl_dim_param, isl_dim_div };
 123         int n_type = sizeof(types)/sizeof(*types);
 124
 125         d = isl_aff_get_denominator_val(aff);
 126         if (!isl_val_is_one(d))
 127                 os << "(";
 128         for (int t = 0; t < n_type; ++t) {
 129                 for (int i = 0; i < isl_aff_dim(aff, types[t]); ++i) {
 130                         v = isl_aff_get_coefficient_val(aff, types[t], i);
 131                         if (isl_val_is_zero(v)) {
 132                                 isl_val_free(v);
 133                                 continue;
 134                         }
 135                         if (!first && isl_val_is_pos(v))
 136                                 os << " + ";
 137                         if (types[t] == isl_dim_div) {
 138                                 isl_aff *div;
 139                                 div = isl_aff_get_div(aff, i);
 140                                 print_term(os, v, div);
 141                         } else {
 142                                 const char *name;
 143                                 name = isl_aff_get_dim_name(aff, types[t], i);
 144                                 print_term(os, v,  name);
 145                         }
 146                         first = false;
 147                         isl_val_free(v);
 148                 }
 149         }
 150
 151         v = isl_aff_get_constant_val(aff);
 152         if (first || !isl_val_is_zero(v)) {
 153                 if (!first && isl_val_is_pos(v))
 154                         os << " + ";
 155                 os << isl_val_get_num_si(v);
 156         }
 157         isl_val_free(v);
 158
 159         if (!isl_val_is_one(d)) {
 160                 os << ")/";
 161                 os << isl_val_get_num_si(d);
 162         }
 163         isl_val_free(d);
 164 }
 165
 166 struct print_pw_aff_data {
 167         std::ostringstream &os;
 168         std::vector<isl_id *> &iterators;
 169         bool first;
 170
 171         print_pw_aff_data(std::ostringstream &os,
 172                 std::vector<isl_id *> &iterators) :
 173                 os(os), iterators(iterators), first(true) {}
 174 };
 175
 176 extern "C" {
 177         static isl_stat print_pw_aff_piece(__isl_take isl_set *set,
 178                 __isl_take isl_aff *aff, void *user);
 179 }
 180
 181 /* Print a single piece of an isl_pw_aff.
 182  * We currently assume that there is only a single piece
 183  * and abort if there happens to be more than one.
 184  */
 185 static isl_stat print_pw_aff_piece(__isl_take isl_set *set,
 186         __isl_take isl_aff *aff, void *user)
 187 {
 188         struct print_pw_aff_data *data = (struct print_pw_aff_data *) user;
 189
 190         assert(data->first);
 191
 192         print_aff_expr(data->os, aff);
 193
 194         data->first = false;
 195
 196         isl_set_free(set);
 197         isl_aff_free(aff);
 198         return isl_stat_ok;
 199 }
 200
 201 static void print_pw_aff_expr(std::ostringstream &os, __isl_keep isl_pw_aff *pa,
 202         std::vector<isl_id *> &iterators)
 203 {
 204         struct print_pw_aff_data data(os, iterators);
 205         isl_pw_aff_foreach_piece(pa, &print_pw_aff_piece, &data);
 206 }
 207
 208 static void writeExpr(xmlTextWriterPtr writer, const char *type,
 209         const char *expr_name, adg_expr *expr, adg *graph)
 210 {
 211         int rc;
 212         std::ostringstream strm;
 213
 214         rc = xmlTextWriterStartElement(writer, BAD_CAST type);
 215         assert(rc >= 0);
 216
 217         assert(expr->name);
 218         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 219                                         BAD_CAST isl_id_get_name(expr->name));
 220         assert(rc >= 0);
 221
 222         assert(expr->expr);
 223         print_pw_aff_expr(strm, expr->expr, graph->iterators);
 224         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST expr_name,
 225                                          BAD_CAST strm.str().c_str());
 226         assert(rc >= 0);
 227
 228         rc = xmlTextWriterEndElement(writer);
 229         assert(rc >= 0);
 230 }
 231
 232 /* Write out the rows of "mat", each prefixed by the integer "ineq".
 233  * The rows are separated by ";".  If first is false, then we
 234  * also include a ";" before the first row.
 235  */
 236 static void writeMatrix(std::ostream &os, __isl_keep isl_mat *mat,
 237         int ineq, bool first)
 238 {
 239         int i, j;
 240         isl_val *v;
 241
 242         for (i = 0; i < isl_mat_rows(mat); ++i) {
 243                 if (!first)
 244                         os << "; ";
 245                 first = false;
 246                 os << ineq;
 247                 for (j = 0; j < isl_mat_cols(mat); ++j) {
 248                         v = isl_mat_get_element_val(mat, i, j);
 249                         os << ", " << isl_val_get_num_si(v);
 250                         isl_val_free(v);
 251                 }
 252         }
 253 }
 254
 255 /* Find the number of dynamic control variables in "space".
 256  *
 257  * The dynamic control variables, if any, are located in the range
 258  * of a wrapped map, with the (possibly lifted) iteration domain
 259  * in the domain.  After adding the dynamic control variables, the
 260  * result may have been lifted as well, so we need dig through
 261  * any possible lifting of the form
 262  *
 263  *      D -> [D -> local[..]]
 264  *
 265  * until we arrive at the iteration domain, in which case there
 266  * are no dynamic control variables, or until we find the control
 267  * variables.
 268  */
 269 static int n_dynamic_in_space(__isl_take isl_space *space)
 270 {
 271         int n;
 272
 273         if (!isl_space_is_wrapping(space)) {
 274                 isl_space_free(space);
 275                 return 0;
 276         }
 277         space = isl_space_unwrap(space);
 278         if (isl_space_has_tuple_id(space, isl_dim_out))
 279                 return n_dynamic_in_space(isl_space_domain(space));
 280         n = isl_space_dim(space, isl_dim_out);
 281         isl_space_free(space);
 282         return n;
 283 }
 284
 285 /* Find the position of the first dynamic control variable in "space".
 286  *
 287  * See n_dynamic_in_space.
 288  */
 289 static int pos_dynamic_in_space(__isl_take isl_space *space)
 290 {
 291         int pos;
 292
 293         if (!isl_space_is_wrapping(space)) {
 294                 isl_space_free(space);
 295                 return 0;
 296         }
 297         space = isl_space_unwrap(space);
 298         if (isl_space_has_tuple_id(space, isl_dim_out))
 299                 return pos_dynamic_in_space(isl_space_domain(space));
 300         pos = isl_space_dim(space, isl_dim_in);
 301         isl_space_free(space);
 302         return pos;
 303 }
 304
 305 /* Write a matrix corresponding to the constraints of "bset".
 306  * The order of the dimensions in the matrix is a follows.
 307  *
 308  *      iterators static_controls dynamic_controls parameters constant
 309  *
 310  * Inside "bset", however, in the set dimensions, the dynamic
 311  * controls may appear in the middle of the static controls.
 312  *
 313  * We therefore need to move the dynamic controls.
 314  * "pos_dynamic" indicates the position of the first dynamic control.
 315  * "n_dynamic" indicates the number of dynamic controls.
 316  */
 317 static void writeMatrix(xmlTextWriterPtr writer, const char *name,
 318         __isl_keep isl_basic_set *bset, int n_dynamic)
 319 {
 320         bool first = true;
 321         int rc;
 322         std::ostringstream strm;
 323         isl_mat *mat;
 324         int n_set = isl_basic_set_dim(bset, isl_dim_set);
 325         int pos_dynamic = pos_dynamic_in_space(isl_basic_set_get_space(bset));
 326
 327         rc = xmlTextWriterStartElement(writer, BAD_CAST name);
 328         assert(rc >= 0);
 329
 330         strm << "[";
 331         mat = isl_basic_set_equalities_matrix(bset,
 332                     isl_dim_set, isl_dim_div, isl_dim_param, isl_dim_cst);
 333         mat = isl_mat_move_cols(mat, n_set - n_dynamic, pos_dynamic, n_dynamic);
 334         writeMatrix(strm, mat, 0, first);
 335         first = isl_mat_rows(mat) == 0;
 336         isl_mat_free(mat);
 337
 338         mat = isl_basic_set_inequalities_matrix(bset,
 339                     isl_dim_set, isl_dim_div, isl_dim_param, isl_dim_cst);
 340         mat = isl_mat_move_cols(mat, n_set - n_dynamic, pos_dynamic, n_dynamic);
 341         writeMatrix(strm, mat, 1, first);
 342         isl_mat_free(mat);
 343         strm << "]";
 344
 345         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "matrix",
 346                                          BAD_CAST strm.str().c_str());
 347         assert(rc >= 0);
 348
 349         rc = xmlTextWriterEndElement(writer);
 350         assert(rc >= 0);
 351 }
 352
 353 /* Print the coefficients of the affine expression "aff",
 354  * separated by commas.
 355  *
 356  * Note that the set dimensions of "aff" are given in the order
 357  *
 358  *      iterators static_and_dynamic_controls
 359  *
 360  * while the coefficients should be printed in the order
 361  *
 362  *      iterators static_controls dynamic_controls parameters constant
 363  */
 364 static void print_aff_coefficients(std::ostringstream &os,
 365         __isl_keep isl_aff *aff)
 366 {
 367         bool first = true;
 368         isl_val *v;
 369         isl_space *space;
 370         int n_index;
 371         int pos_dynamic;
 372         int n_dynamic;
 373
 374         space = isl_aff_get_domain_space(aff);
 375         pos_dynamic = pos_dynamic_in_space(isl_space_copy(space));
 376         n_dynamic = n_dynamic_in_space(space);
 377         n_index = isl_aff_dim(aff, isl_dim_in) - n_dynamic;
 378
 379         for (int i = 0; i < pos_dynamic; ++i) {
 380                 if (!first)
 381                         os << ", ";
 382                 v = isl_aff_get_coefficient_val(aff, isl_dim_in, i);
 383                 os << isl_val_get_num_si(v);
 384                 isl_val_free(v);
 385                 first = false;
 386         }
 387
 388         for (int i = pos_dynamic; i < n_index; ++i) {
 389                 if (!first)
 390                         os << ", ";
 391                 v = isl_aff_get_coefficient_val(aff, isl_dim_in, n_dynamic + i);
 392                 os << isl_val_get_num_si(v);
 393                 isl_val_free(v);
 394                 first = false;
 395         }
 396
 397         for (int i = 0; i < n_dynamic; ++i) {
 398                 if (!first)
 399                         os << ", ";
 400                 v = isl_aff_get_coefficient_val(aff, isl_dim_in,
 401                                                         pos_dynamic + i);
 402                 os << isl_val_get_num_si(v);
 403                 isl_val_free(v);
 404                 first = false;
 405         }
 406
 407         for (int i = 0; i < isl_aff_dim(aff, isl_dim_param); ++i) {
 408                 if (!first)
 409                         os << ", ";
 410                 v = isl_aff_get_coefficient_val(aff, isl_dim_param, i);
 411                 os << isl_val_get_num_si(v);
 412                 isl_val_free(v);
 413                 first = false;
 414         }
 415
 416         if (!first)
 417                 os << ", ";
 418         v = isl_aff_get_constant_val(aff);
 419         os << isl_val_get_num_si(v);
 420         isl_val_free(v);
 421 }
 422
 423 /* Write out "map" in the form of a matrix, with each row
 424  * corresponding to an affine expression.
 425  */
 426 static void writeMatrix(xmlTextWriterPtr writer, const char *name,
 427         __isl_keep isl_multi_aff *map)
 428 {
 429         int rc;
 430         std::ostringstream strm;
 431         int n;
 432
 433         rc = xmlTextWriterStartElement(writer, BAD_CAST name);
 434         assert(rc >= 0);
 435
 436         strm << "[";
 437         n = isl_multi_aff_dim(map, isl_dim_out);
 438         for (int i = 0; i < n; ++i) {
 439                 isl_aff *aff;
 440                 if (i)
 441                         strm << "; ";
 442                 aff = isl_multi_aff_get_aff(map, i);
 443                 print_aff_coefficients(strm, aff);
 444                 isl_aff_free(aff);
 445         }
 446         strm << "]";
 447
 448         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "matrix",
 449                                          BAD_CAST strm.str().c_str());
 450         assert(rc >= 0);
 451
 452         rc = xmlTextWriterEndElement(writer);
 453         assert(rc >= 0);
 454 }
 455
 456 struct write_bound_data {
 457         xmlTextWriterPtr writer;
 458         adg_domain *domain;
 459         adg *graph;
 460 };
 461
 462 static isl_stat write_bound(__isl_take isl_basic_set *bset, void *user)
 463 {
 464         int rc;
 465         int nparam;
 466         std::ostringstream strm;
 467         write_bound_data *data = (write_bound_data *) user;
 468         xmlTextWriterPtr writer = data->writer;
 469
 470         rc = xmlTextWriterStartElement(writer, BAD_CAST "linearbound");
 471         assert(rc >= 0);
 472
 473         for (int i = 0; i < data->graph->iterators.size(); ++i) {
 474                 if (i)
 475                         strm << ", ";
 476                 strm << isl_id_get_name(data->graph->iterators[i]);
 477         }
 478
 479         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "index",
 480                                          BAD_CAST strm.str().c_str());
 481         assert(rc >= 0);
 482
 483         strm.str("");
 484         for (int i = 0; i < data->domain->controls.size(); ++i) {
 485                 if (i)
 486                         strm << ", ";
 487                 strm << isl_id_get_name(data->domain->controls[i]->name);
 488         }
 489         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "staticControl",
 490                                          BAD_CAST strm.str().c_str());
 491         assert(rc >= 0);
 492
 493         strm.str("");
 494         for (int i = 0; i < data->domain->filters.size(); ++i) {
 495                 if (i)
 496                         strm << ", ";
 497                 strm << data->domain->filters[i]->get_expr();
 498         }
 499         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "dynamicControl",
 500                                          BAD_CAST strm.str().c_str());
 501         assert(rc >= 0);
 502
 503         strm.str("");
 504         nparam = isl_basic_set_dim(bset, isl_dim_param);
 505         for (int i = 0; i < nparam; ++i) {
 506                 if (i)
 507                         strm << ", ";
 508                 strm << isl_basic_set_get_dim_name(bset, isl_dim_param, i);
 509         }
 510         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "parameter",
 511                                          BAD_CAST strm.str().c_str());
 512         assert(rc >= 0);
 513
 514         bset = isl_basic_set_remove_redundancies(bset);
 515         writeMatrix(writer, "constraint", bset, data->domain->filters.size());
 516
 517         isl_basic_set_free(bset);
 518
 519         if (data->graph->context &&
 520             !isl_set_plain_is_universe(data->graph->context)) {
 521                 assert(isl_set_n_basic_set(data->graph->context) == 1);
 522                 bset = isl_set_simple_hull(isl_set_copy(data->graph->context));
 523                 bset = isl_basic_set_remove_redundancies(bset);
 524                 writeMatrix(writer, "context", bset, 0);
 525                 isl_basic_set_free(bset);
 526         }
 527
 528         for (int i = 0; i < data->domain->controls.size(); ++i)
 529                 writeExpr(writer, "control", "exp", data->domain->controls[i],
 530                             data->graph);
 531
 532         rc = xmlTextWriterEndElement(writer);
 533         assert(rc >= 0);
 534
 535         return isl_stat_ok;
 536 }
 537
 538 static void writeDomain(xmlTextWriterPtr writer, adg_domain *domain, adg *graph)
 539 {
 540         int rc;
 541         write_bound_data data = { writer, domain, graph };
 542
 543         rc = xmlTextWriterStartElement(writer, BAD_CAST "domain");
 544         assert(rc >= 0);
 545
 546         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "type",
 547                                                 BAD_CAST "LBS");
 548         assert(rc >= 0);
 549
 550         rc = isl_set_foreach_basic_set(domain->bounds, &write_bound, &data);
 551         assert(rc >= 0);
 552
 553         rc = xmlTextWriterEndElement(writer);
 554         assert(rc >= 0);
 555 }
 556
 557 static void writePort(xmlTextWriterPtr writer, adg_port *port, bool output,
 558         adg *graph)
 559 {
 560         int rc;
 561         const char *type;
 562
 563         type = output ? "outport" : "inport";
 564
 565         rc = xmlTextWriterStartElement(writer, BAD_CAST type);
 566         assert(rc >= 0);
 567
 568         assert(port->name);
 569         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 570                                          BAD_CAST isl_id_get_name(port->name));
 571         assert(port->node_name);
 572         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "node",
 573                                      BAD_CAST isl_id_get_name(port->node_name));
 574         assert(port->edge_name);
 575         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "edge",
 576                                      BAD_CAST isl_id_get_name(port->edge_name));
 577
 578         for (int i = 0; i < port->vars.size(); ++i)
 579                 writeVar(writer, "bindvariable", port->vars[i]);
 580
 581         writeDomain(writer, port->domain, graph);
 582
 583         rc = xmlTextWriterEndElement(writer);
 584         assert(rc >= 0);
 585 }
 586
 587 static void writeGate(xmlTextWriterPtr writer, adg_gate *gate, adg *graph)
 588 {
 589         int rc;
 590
 591         rc = xmlTextWriterStartElement(writer, BAD_CAST "invar");
 592         assert(rc >= 0);
 593
 594         assert(gate->name);
 595         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 596                                          BAD_CAST isl_id_get_name(gate->name));
 597
 598         assert(gate->in && gate->in->access);
 599         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "realName",
 600                                          BAD_CAST gate->in->get_expr());
 601
 602         assert(gate->out);
 603         writeVar(writer, "bindvariable", gate->out);
 604
 605         writeDomain(writer, gate->domain, graph);
 606
 607         rc = xmlTextWriterEndElement(writer);
 608         assert(rc >= 0);
 609 }
 610
 611 static void writeFunction(xmlTextWriterPtr writer, adg_function *fn, adg *graph)
 612 {
 613         int rc;
 614
 615         rc = xmlTextWriterStartElement(writer, BAD_CAST "function");
 616         assert(rc >= 0);
 617
 618         assert(fn->name);
 619         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 620                                          BAD_CAST isl_id_get_name(fn->name));
 621
 622         for (int i = 0; i < fn->in.size(); ++i)
 623                 writeArg(writer, "inargument", fn->in[i]);
 624         for (int i = 0; i < fn->out.size(); ++i)
 625                 writeArg(writer, "outargument", fn->out[i]);
 626         for (int i = 0; i < fn->ctrl.size(); ++i)
 627                 writeExpr(writer, "ctrlvar", "iterator", fn->ctrl[i], graph);
 628
 629         writeDomain(writer, fn->domain, graph);
 630
 631         rc = xmlTextWriterEndElement(writer);
 632         assert(rc >= 0);
 633 }
 634
 635 /* The gates should be printed after the input ports because
 636  * they may use data read through an input port.
 637  */
 638 static void writeNode(xmlTextWriterPtr writer, adg_node *node, adg *graph)
 639 {
 640         int rc;
 641
 642         rc = xmlTextWriterStartElement(writer, BAD_CAST "node");
 643         assert(rc >= 0);
 644
 645         assert(node->name);
 646         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 647                                          BAD_CAST isl_id_get_name(node->name));
 648         assert(rc >= 0);
 649         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "levelUpNode",
 650                                         BAD_CAST "");
 651         assert(rc >= 0);
 652
 653         for (int i = 0; i < node->input_ports.size(); ++i)
 654                 writePort(writer, node->input_ports[i], false, graph);
 655
 656         for (int i = 0; i < node->gates.size(); ++i)
 657                 writeGate(writer, node->gates[i], graph);
 658
 659         for (int i = 0; i < node->output_ports.size(); ++i)
 660                 writePort(writer, node->output_ports[i], true, graph);
 661
 662         for (int i = 0; i < node->expressions.size(); ++i)
 663                 writeExpr(writer, "expression", "value",
 664                                 node->expressions[i], graph);
 665
 666         writeFunction(writer, node->function, graph);
 667
 668         writeDomain(writer, node->domain, graph);
 669
 670         rc = xmlTextWriterEndElement(writer);
 671         assert(rc >= 0);
 672 }
 673
 674 static void writeEdge(xmlTextWriterPtr writer, adg_edge *edge)
 675 {
 676         int rc;
 677         std::ostringstream strm;
 678         char *s;
 679
 680         rc = xmlTextWriterStartElement(writer, BAD_CAST "edge");
 681         assert(rc >= 0);
 682
 683         assert(edge->name);
 684         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 685                                          BAD_CAST isl_id_get_name(edge->name));
 686         assert(rc >= 0);
 687
 688         assert(edge->from_port_name);
 689         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "fromPort",
 690                              BAD_CAST isl_id_get_name(edge->from_port_name));
 691         assert(rc >= 0);
 692
 693         assert(edge->from_node_name);
 694         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "fromNode",
 695                              BAD_CAST isl_id_get_name(edge->from_node_name));
 696         assert(rc >= 0);
 697
 698         assert(edge->to_port_name);
 699         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "toPort",
 700                              BAD_CAST isl_id_get_name(edge->to_port_name));
 701         assert(rc >= 0);
 702
 703         assert(edge->to_node_name);
 704         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "toNode",
 705                              BAD_CAST isl_id_get_name(edge->to_node_name));
 706         assert(rc >= 0);
 707
 708         s = isl_val_to_str(edge->value_size);
 709         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "size", BAD_CAST s);
 710         free(s);
 711         assert(rc >= 0);
 712
 713         rc = xmlTextWriterStartElement(writer, BAD_CAST "linearization");
 714         assert(rc >= 0);
 715
 716         switch (edge->type) {
 717         case adg_edge_fifo:
 718                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "type",
 719                                                  BAD_CAST "fifo");
 720                 break;
 721         case adg_edge_sticky_fifo:
 722                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "type",
 723                                                  BAD_CAST "sticky_fifo");
 724                 break;
 725         case adg_edge_shift_register:
 726                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "type",
 727                                                  BAD_CAST "shift_register");
 728                 break;
 729         case adg_edge_broadcast:
 730                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "type",
 731                                                  BAD_CAST "BroadcastInOrder");
 732                 break;
 733         case adg_edge_generic:
 734                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "type",
 735                                                  BAD_CAST "GenericOutOfOrder");
 736                 break;
 737         case adg_edge_error:
 738                 assert(0);
 739                 break;
 740         }
 741         assert(rc >= 0);
 742
 743         rc = xmlTextWriterEndElement(writer);
 744         assert(rc >= 0);
 745
 746         writeMatrix(writer, "mapping", edge->map);
 747
 748         rc = xmlTextWriterEndElement(writer);
 749         assert(rc >= 0);
 750 }
 751
 752 static void writeParam(xmlTextWriterPtr writer, adg_param *param, adg *graph)
 753 {
 754         int rc;
 755         std::ostringstream strm;
 756
 757         rc = xmlTextWriterStartElement(writer, BAD_CAST "parameter");
 758         assert(rc >= 0);
 759
 760         assert(param->name);
 761         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 762                                          BAD_CAST isl_id_get_name(param->name));
 763         assert(rc >= 0);
 764
 765         if (param->lb) {
 766                 strm.str("");
 767                 print_aff_expr(strm, param->lb);
 768                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "lb",
 769                                                  BAD_CAST strm.str().c_str());
 770                 assert(rc >= 0);
 771         }
 772
 773         if (param->ub) {
 774                 strm.str("");
 775                 print_aff_expr(strm, param->ub);
 776                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "ub",
 777                                                  BAD_CAST strm.str().c_str());
 778                 assert(rc >= 0);
 779         }
 780
 781         if (param->val) {
 782                 strm.str("");
 783                 print_aff_expr(strm, param->val);
 784                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "value",
 785                                                  BAD_CAST strm.str().c_str());
 786                 assert(rc >= 0);
 787         }
 788
 789         rc = xmlTextWriterEndElement(writer);
 790         assert(rc >= 0);
 791 }
 792
 793 static void writeADG(xmlTextWriterPtr writer, adg *graph)
 794 {
 795         int rc;
 796
 797         rc = xmlTextWriterStartElement(writer, BAD_CAST "adg");
 798         assert(rc >= 0);
 799
 800         assert(graph->name);
 801         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 802                                          BAD_CAST isl_id_get_name(graph->name));
 803         assert(rc >= 0);
 804         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "levelUpNode",
 805                                         BAD_CAST "");
 806         assert(rc >= 0);
 807
 808         for (int i = 0; i < graph->params.size(); ++i)
 809                 writeParam(writer, graph->params[i], graph);
 810
 811         for (int i = 0; i < graph->nodes.size(); ++i)
 812                 writeNode(writer, graph->nodes[i], graph);
 813
 814         for (int i = 0; i < graph->edges.size(); ++i)
 815                 writeEdge(writer, graph->edges[i]);
 816
 817         rc = xmlTextWriterEndElement(writer);
 818         assert(rc >= 0);
 819 }
 820
 821 /* Project out all the lifted variables that used to be
 822  * existentially quantified.  In other words, undo the lifting.
 823  * Also project out the dynamic control variables.
 824  */
 825 static __isl_give isl_set *unwrap(__isl_take isl_set *dom)
 826 {
 827         if (!isl_set_is_wrapping(dom))
 828                 return dom;
 829         return unwrap(isl_map_domain(isl_set_unwrap(dom)));
 830 }
 831
 832 /* Project out all the lifted variables that used to be
 833  * existentially quantified.  In other words, undo the lifting.
 834  * Turn the dynamic control variables into parameters.
 835  * The names of those parameters are taken from "filters".
 836  */
 837 static __isl_give isl_set *unwrap_filtered(__isl_take isl_set *dom,
 838         std::vector<adg_var *> &filters)
 839 {
 840         int i, n;
 841         unsigned nparam;
 842         isl_map *map;
 843
 844         if (!isl_set_is_wrapping(dom))
 845                 return dom;
 846
 847         map = isl_set_unwrap(dom);
 848         if (isl_map_has_tuple_name(map, isl_dim_out))
 849                 return unwrap_filtered(isl_map_domain(map), filters);
 850
 851         nparam = isl_map_dim(map, isl_dim_param);
 852         n = filters.size();
 853         map = isl_map_add_dims(map, isl_dim_param, n);
 854         for (i = 0; i < n; ++i) {
 855                 isl_id *id;
 856
 857                 id = isl_pw_multi_aff_get_tuple_id(filters[i]->access,
 858                                                 isl_dim_out);
 859                 map = isl_map_set_dim_id(map, isl_dim_param, nparam + i, id);
 860                 map = isl_map_equate(map, isl_dim_param, nparam + i,
 861                                         isl_dim_out, i);
 862         }
 863
 864         return unwrap(isl_map_domain(map));
 865 }
 866
 867 /* Construct a schedule by adding an extra pair of dimensions to
 868  * domain->schedule, fixed to "offset1" and "offset2"
 869  * and setting the input name to "name".
 870  *
 871  * If "filtered" is set, then the dynamic control variables are preserved
 872  * (as parameters) in the resulting schedule.
 873  */
 874 static __isl_give isl_map *domain_schedule(adg_node *node, adg_domain *domain,
 875         int offset1, int offset2, __isl_take isl_id *name, bool filtered)
 876 {
 877         isl_set *dom;
 878         isl_map *sched;
 879         int n_out;
 880
 881         n_out = isl_map_dim(node->schedule, isl_dim_out);
 882
 883         dom = isl_set_copy(domain->bounds);
 884         if (filtered)
 885                 dom = unwrap_filtered(dom, domain->filters);
 886         else
 887                 dom = unwrap(dom);
 888
 889         sched = isl_map_copy(node->schedule);
 890         sched = isl_map_intersect_domain(sched, dom);
 891         sched = isl_map_add_dims(sched, isl_dim_out, 2);
 892         sched = isl_map_fix_si(sched, isl_dim_out, n_out, offset1);
 893         sched = isl_map_fix_si(sched, isl_dim_out, n_out + 1, offset2);
 894         sched = isl_map_set_tuple_id(sched, isl_dim_in, name);
 895
 896         return sched;
 897 }
 898
 899 static __isl_give isl_map *port_schedule(adg_node *node, adg_port *port,
 900         int offset, bool filtered)
 901 {
 902         return domain_schedule(node, port->domain, offset, port->arg_pos,
 903                                 isl_id_copy(port->name), filtered);
 904 }
 905
 906 static __isl_give isl_map *gate_schedule(adg_node *node, adg_gate *gate,
 907         int offset, bool filtered)
 908 {
 909         return domain_schedule(node, gate->domain, offset, 0,
 910                                 isl_id_copy(gate->name), filtered);
 911 }
 912
 913 /* Construct a schedule for all elements in the node.
 914  * We add an extra dimension to node->schedule to ensure that
 915  * the different elements are executed in the right order:
 916  * input ports, gates, function, output ports.
 917  * The input ports themselves are ordered according to the access nr.
 918  *
 919  * If "filtered" is set, then the dynamic control variables are preserved
 920  * (as parameters) in the resulting schedule.
 921  */
 922 static __isl_give isl_union_map *collect_node_schedule(adg_node *node, int n,
 923         bool filtered)
 924 {
 925         isl_map *sched_f;
 926         isl_union_map *sched;
 927         int n_out;
 928
 929         n_out = isl_map_dim(node->schedule, isl_dim_out);
 930
 931         sched_f = domain_schedule(node, node->function->domain, 4 * n + 2, 0,
 932                                 isl_id_copy(node->name), filtered);
 933         sched = isl_union_map_from_map(sched_f);
 934
 935         for (int i = 0; i < node->input_ports.size(); ++i) {
 936                 isl_map *sched_p;
 937                 sched_p = port_schedule(node, node->input_ports[i], 4 * n + 0,
 938                                         filtered);
 939                 sched = isl_union_map_add_map(sched, sched_p);
 940         }
 941
 942         for (int i = 0; i < node->gates.size(); ++i) {
 943                 isl_map *sched_p;
 944                 sched_p = gate_schedule(node, node->gates[i], 4 * n + 1,
 945                                         filtered);
 946                 sched = isl_union_map_add_map(sched, sched_p);
 947         }
 948
 949         for (int i = 0; i < node->output_ports.size(); ++i) {
 950                 isl_map *sched_p;
 951                 sched_p = port_schedule(node, node->output_ports[i], 4 * n + 3,
 952                                         filtered);
 953                 sched = isl_union_map_add_map(sched, sched_p);
 954         }
 955
 956         return sched;
 957 }
 958
 959 /* Construct a schedule for all nodes in the graph.
 960  *
 961  * If "filtered" is set, then the dynamic control variables are preserved
 962  * (as parameters) in the resulting schedule.
 963  */
 964 static isl_union_map *collect_schedule(adg *graph, bool filtered)
 965 {
 966         isl_space *space = isl_set_get_space(graph->context);
 967         isl_union_map *sched = isl_union_map_empty(space);
 968
 969         for (int i = 0; i < graph->nodes.size(); ++i) {
 970                 isl_union_map *sched_i;
 971                 sched_i = collect_node_schedule(graph->nodes[i], i, filtered);
 972                 sched = isl_union_map_union(sched, sched_i);
 973         }
 974
 975         return sched;
 976 }
 977
 978 /* Set the "atomic" option on all the dimensions of a schedule
 979  * of dimension "sched_len".
 980  */
 981 static __isl_give isl_ast_build *set_atomic(
 982         __isl_take isl_ast_build *context, int sched_len)
 983 {
 984         isl_ctx *ctx;
 985         isl_space *space;
 986         isl_union_map *opt;
 987
 988         ctx = isl_ast_build_get_ctx(context);
 989
 990         space = isl_space_alloc(ctx, 0, sched_len, 1);
 991         space = isl_space_set_tuple_name(space, isl_dim_out, "atomic");
 992         opt = isl_union_map_from_map(isl_map_universe(space));
 993
 994         context = isl_ast_build_set_options(context, opt);
 995
 996         return context;
 997 }
 998
 999 /* This function is called for each leaf in the AST constructed
1000  * from the schedule without dynamic control variables.
1001  * Continue constructing an inner AST for the schedule with
1002  * the dynamic control variables as parameters.
1003  */
1004 static __isl_give isl_ast_node *create_leaf(__isl_take isl_ast_build *build,
1005         void *user)
1006 {
1007         isl_ast_node *tree;
1008         isl_union_map *sched;
1009         isl_union_map *sched2 = (isl_union_map *) user;
1010
1011         sched = isl_ast_build_get_schedule(build);
1012         sched = isl_union_map_range_product(sched, isl_union_map_copy(sched2));
1013         tree = isl_ast_build_ast_from_schedule(build, sched);
1014         isl_ast_build_free(build);
1015
1016         return tree;
1017 }
1018
1019 /* Does the adg contain any dynamic control variables?
1020  */
1021 static bool any_filters(adg *graph)
1022 {
1023         for (int i = 0; i < graph->nodes.size(); ++i) {
1024                 adg_node *node = graph->nodes[i];
1025
1026                 for (int j = 0; j < node->input_ports.size(); ++j)
1027                         if (node->input_ports[j]->domain->filters.size() > 0)
1028                                 return true;
1029                 for (int j = 0; j < node->gates.size(); ++j)
1030                         if (node->gates[j]->domain->filters.size() > 0)
1031                                 return true;
1032                 for (int j = 0; j < node->output_ports.size(); ++j)
1033                         if (node->output_ports[j]->domain->filters.size() > 0)
1034                                 return true;
1035         }
1036
1037         return false;
1038 }
1039
1040 /* Construct a schedule, convert it to an AST and then
1041  * write out the AST using writeAST.
1042  *
1043  * To handle dynamic control variables, we construct two schedules,
1044  * one (sched) with the dynamic control variables projected out and
1045  * one (sched2) with the dynamic control variables as parameters.
1046  *
1047  * We construct an AST for the first schedule and within each leaf
1048  * of the AST, we construct an AST for the second schedule.
1049  * This inner AST will essentially reflect the conditions on
1050  * the dynamic control variables.
1051  *
1052  * Note that we only need to create this second schedule if there actually
1053  * are any dynamic control variables.
1054  */
1055 static void writeAST(xmlTextWriterPtr writer, adg *graph)
1056 {
1057         int rc;
1058         isl_ctx *ctx = isl_set_get_ctx(graph->context);
1059         isl_union_map *sched, *sched2 = NULL;
1060         isl_ast_build *build;
1061         isl_ast_node *tree;
1062         isl_id_list *iterators;
1063         bool has_filters;
1064
1065         isl_options_set_ast_build_atomic_upper_bound(ctx, 1);
1066         isl_options_set_ast_build_prefer_pdiv(ctx, 1);
1067         isl_options_set_ast_build_allow_else(ctx, 0);
1068         isl_options_set_ast_build_allow_or(ctx, 0);
1069
1070         has_filters = any_filters(graph);
1071
1072         sched = collect_schedule(graph, false);
1073         if (has_filters)
1074                 sched2 = collect_schedule(graph, true);
1075
1076         iterators = isl_id_list_alloc(ctx, graph->all_iterators.size());
1077         for (int i = 0; i < graph->all_iterators.size(); ++i)
1078                 iterators = isl_id_list_add(iterators,
1079                                         isl_id_copy(graph->all_iterators[i]));
1080         build = isl_ast_build_from_context(isl_set_copy(graph->context));
1081         build = isl_ast_build_set_iterators(build, iterators);
1082         if (has_filters)
1083                 build = isl_ast_build_set_create_leaf(build,
1084                                                         &create_leaf, sched2);
1085         build = set_atomic(build, graph->all_iterators.size() + 2);
1086         tree = isl_ast_build_ast_from_schedule(build, sched);
1087         isl_ast_build_free(build);
1088
1089         writeAST(writer, tree);
1090
1091         isl_union_map_free(sched2);
1092         isl_ast_node_free(tree);
1093 }
1094
1095 /* Write out an XML representation of "graph" to "out".
1096  * The adg part is obtained by scanning the data structure.
1097  * The ast part is obtained by generating code based on the domain schedules.
1098  */
1099 void adg_print_xml(adg *graph, FILE *out)
1100 {
1101         int rc;
1102         xmlTextWriterPtr writer;
1103         xmlDocPtr doc;
1104
1105         LIBXML_TEST_VERSION
1106
1107         writer = xmlNewTextWriterDoc(&doc, 0);
1108         assert(writer);
1109
1110         rc = xmlTextWriterStartDocument(writer, NULL, NULL, NULL);
1111         assert(rc >= 0);
1112
1113         rc = xmlTextWriterStartDTD(writer, BAD_CAST "sadg",
1114                         BAD_CAST "-//LIACS//DTD ESPAM 1//EN",
1115                         BAD_CAST "http://www.liacs.nl/~cserc/dtd/espam_1.dtd");
1116         assert(rc >= 0);
1117         rc = xmlTextWriterEndDTD(writer);
1118         assert(rc >= 0);
1119
1120         rc = xmlTextWriterStartElement(writer, BAD_CAST "sadg");
1121         assert(rc >= 0);
1122
1123         writeADG(writer, graph);
1124         writeAST(writer, graph);
1125
1126         rc = xmlTextWriterEndElement(writer);
1127         assert(rc >= 0);
1128
1129         rc = xmlTextWriterEndDocument(writer);
1130         assert(rc >= 0);
1131
1132         xmlFreeTextWriter(writer);
1133
1134         rc = xmlDocFormatDump(out, doc, 1);
1135         assert(rc >= 0);
1136 }