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