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/union_map.h>
   9 #include <cloog/isl/cloog.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_int v, const char *name)
  76 {
  77         if (!isl_int_is_one(v)) {
  78                 os << isl_int_get_si(v);
  79                 os << "*";
  80         }
  81         os << name;
  82 }
  83
  84 static void print_aff_expr(std::ostringstream &os, __isl_keep isl_aff *aff);
  85
  86 /* Print "v * div(aff)" onto os.
  87  */
  88 static void print_term(std::ostringstream &os, isl_int v,
  89         __isl_take isl_aff *aff)
  90 {
  91         isl_int d;
  92
  93         isl_int_init(d);
  94
  95         os << "div(";
  96         print_aff_expr(os, aff);
  97         os << ",";
  98         isl_aff_get_denominator(aff, &d);
  99         os << isl_int_get_si(d);
 100         os << ")";
 101         isl_int_clear(d);
 102         isl_aff_free(aff);
 103 }
 104
 105 /* Print "aff" onto os.
 106  */
 107 static void print_aff_expr(std::ostringstream &os, __isl_keep isl_aff *aff)
 108 {
 109         bool first = true;
 110         isl_int v;
 111         enum isl_dim_type types[] = { isl_dim_in, isl_dim_param, isl_dim_div };
 112         int n_type = sizeof(types)/sizeof(*types);
 113
 114         isl_int_init(v);
 115
 116         for (int t = 0; t < n_type; ++t) {
 117                 for (int i = 0; i < isl_aff_dim(aff, types[t]); ++i) {
 118                         isl_aff_get_coefficient(aff, types[t], i, &v);
 119                         if (isl_int_is_zero(v))
 120                                 continue;
 121                         if (!first && isl_int_is_pos(v))
 122                                 os << " + ";
 123                         if (types[t] == isl_dim_div) {
 124                                 isl_aff *div;
 125                                 div = isl_aff_get_div(aff, i);
 126                                 print_term(os, v, div);
 127                         } else {
 128                                 const char *name;
 129                                 name = isl_aff_get_dim_name(aff, types[t], i);
 130                                 print_term(os, v,  name);
 131                         }
 132                         first = false;
 133                 }
 134         }
 135
 136         isl_aff_get_constant(aff, &v);
 137         if (first || !isl_int_is_zero(v)) {
 138                 if (!first && isl_int_is_pos(v))
 139                         os << " + ";
 140                 os << isl_int_get_si(v);
 141         }
 142
 143         isl_int_clear(v);
 144 }
 145
 146 struct print_pw_aff_data {
 147         std::ostringstream &os;
 148         std::vector<isl_id *> &iterators;
 149         bool first;
 150
 151         print_pw_aff_data(std::ostringstream &os,
 152                 std::vector<isl_id *> &iterators) :
 153                 os(os), iterators(iterators), first(true) {}
 154 };
 155
 156 extern "C" {
 157         static int print_pw_aff_piece(__isl_take isl_set *set,
 158                 __isl_take isl_aff *aff, void *user);
 159 }
 160
 161 /* Print a single piece of an isl_pw_aff.
 162  * We currently assume that there is only a single piece
 163  * and abort if there happens to be more than one.
 164  */
 165 static int print_pw_aff_piece(__isl_take isl_set *set,
 166         __isl_take isl_aff *aff, void *user)
 167 {
 168         struct print_pw_aff_data *data = (struct print_pw_aff_data *) user;
 169
 170         assert(data->first);
 171
 172         print_aff_expr(data->os, aff);
 173
 174         data->first = false;
 175
 176         isl_set_free(set);
 177         isl_aff_free(aff);
 178         return 0;
 179 }
 180
 181 static void print_pw_aff_expr(std::ostringstream &os, __isl_keep isl_pw_aff *pa,
 182         std::vector<isl_id *> &iterators)
 183 {
 184         struct print_pw_aff_data data(os, iterators);
 185         isl_pw_aff_foreach_piece(pa, &print_pw_aff_piece, &data);
 186 }
 187
 188 static void writeExpr(xmlTextWriterPtr writer, const char *type,
 189         const char *expr_name, adg_expr *expr, adg *graph)
 190 {
 191         int rc;
 192         std::ostringstream strm;
 193
 194         rc = xmlTextWriterStartElement(writer, BAD_CAST type);
 195         assert(rc >= 0);
 196
 197         assert(expr->name);
 198         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 199                                         BAD_CAST isl_id_get_name(expr->name));
 200         assert(rc >= 0);
 201
 202         assert(expr->expr);
 203         print_pw_aff_expr(strm, expr->expr, graph->iterators);
 204         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST expr_name,
 205                                          BAD_CAST strm.str().c_str());
 206         assert(rc >= 0);
 207
 208         rc = xmlTextWriterEndElement(writer);
 209         assert(rc >= 0);
 210 }
 211
 212 /* Write out the rows of "mat", each prefixed by the integer "ineq".
 213  * The rows are separated by ";".  If first is false, then we
 214  * also include a ";" before the first row.
 215  */
 216 static void writeMatrix(std::ostream &os, __isl_keep isl_mat *mat,
 217         int ineq, bool first)
 218 {
 219         int i, j;
 220         isl_int v;
 221
 222         isl_int_init(v);
 223         for (i = 0; i < isl_mat_rows(mat); ++i) {
 224                 if (!first)
 225                         os << "; ";
 226                 first = false;
 227                 os << ineq;
 228                 for (j = 0; j < isl_mat_cols(mat); ++j) {
 229                         isl_mat_get_element(mat, i, j, &v);
 230                         os << ", " << isl_int_get_si(v);
 231                 }
 232         }
 233         isl_int_clear(v);
 234 }
 235
 236 /* Find the number of dynamic control variables in "space".
 237  *
 238  * The dynamic control variables, if any, are located in the range
 239  * of a wrapped map, with the (possibly lifted) iteration domain
 240  * in the domain.  After adding the dynamic control variables, the
 241  * result may have been lifted as well, so we need dig through
 242  * any possible lifting of the form
 243  *
 244  *      D -> [D -> local[..]]
 245  *
 246  * until we arrive at the iteration domain, in which case there
 247  * are no dynamic control variables, or until we find the control
 248  * variables.
 249  */
 250 static int n_dynamic_in_space(__isl_take isl_space *space)
 251 {
 252         int n;
 253
 254         if (!isl_space_is_wrapping(space)) {
 255                 isl_space_free(space);
 256                 return 0;
 257         }
 258         space = isl_space_unwrap(space);
 259         if (isl_space_has_tuple_id(space, isl_dim_out))
 260                 return n_dynamic_in_space(isl_space_domain(space));
 261         n = isl_space_dim(space, isl_dim_out);
 262         isl_space_free(space);
 263         return n;
 264 }
 265
 266 /* Find the position of the first dynamic control variable in "space".
 267  *
 268  * See n_dynamic_in_space.
 269  */
 270 static int pos_dynamic_in_space(__isl_take isl_space *space)
 271 {
 272         int pos;
 273
 274         if (!isl_space_is_wrapping(space)) {
 275                 isl_space_free(space);
 276                 return 0;
 277         }
 278         space = isl_space_unwrap(space);
 279         if (isl_space_has_tuple_id(space, isl_dim_out))
 280                 return pos_dynamic_in_space(isl_space_domain(space));
 281         pos = isl_space_dim(space, isl_dim_in);
 282         isl_space_free(space);
 283         return pos;
 284 }
 285
 286 /* Write a matrix corresponding to the constraints of "bset".
 287  * The order of the dimensions in the matrix is a follows.
 288  *
 289  *      iterators static_controls dynamic_controls parameters constant
 290  *
 291  * Inside "bset", however, in the set dimensions, the dynamic
 292  * controls may appear in the middle of the static controls.
 293  *
 294  * We therefore need to move the dynamic controls.
 295  * "pos_dynamic" indicates the position of the first dynamic control.
 296  * "n_dynamic" indicates the number of dynamic controls.
 297  */
 298 static void writeMatrix(xmlTextWriterPtr writer, const char *name,
 299         __isl_keep isl_basic_set *bset, int n_dynamic)
 300 {
 301         bool first = true;
 302         int rc;
 303         std::ostringstream strm;
 304         isl_mat *mat;
 305         int n_set = isl_basic_set_dim(bset, isl_dim_set);
 306         int pos_dynamic = pos_dynamic_in_space(isl_basic_set_get_space(bset));
 307
 308         rc = xmlTextWriterStartElement(writer, BAD_CAST name);
 309         assert(rc >= 0);
 310
 311         strm << "[";
 312         mat = isl_basic_set_equalities_matrix(bset,
 313                     isl_dim_set, isl_dim_div, isl_dim_param, isl_dim_cst);
 314         mat = isl_mat_move_cols(mat, n_set - n_dynamic, pos_dynamic, n_dynamic);
 315         writeMatrix(strm, mat, 0, first);
 316         first = isl_mat_rows(mat) == 0;
 317         isl_mat_free(mat);
 318
 319         mat = isl_basic_set_inequalities_matrix(bset,
 320                     isl_dim_set, isl_dim_div, isl_dim_param, isl_dim_cst);
 321         mat = isl_mat_move_cols(mat, n_set - n_dynamic, pos_dynamic, n_dynamic);
 322         writeMatrix(strm, mat, 1, first);
 323         isl_mat_free(mat);
 324         strm << "]";
 325
 326         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "matrix",
 327                                          BAD_CAST strm.str().c_str());
 328         assert(rc >= 0);
 329
 330         rc = xmlTextWriterEndElement(writer);
 331         assert(rc >= 0);
 332 }
 333
 334 /* Print the coefficients of the affine expression "aff",
 335  * separated by commas.
 336  *
 337  * Note that the set dimensions of "aff" are given in the order
 338  *
 339  *      iterators static_and_dynamic_controls
 340  *
 341  * while the coefficients should be printed in the order
 342  *
 343  *      iterators static_controls dynamic_controls parameters constant
 344  */
 345 static void print_aff_coefficients(std::ostringstream &os,
 346         __isl_keep isl_aff *aff)
 347 {
 348         bool first = true;
 349         isl_int v;
 350         isl_space *space;
 351         int n_index;
 352         int pos_dynamic;
 353         int n_dynamic;
 354
 355         space = isl_aff_get_domain_space(aff);
 356         pos_dynamic = pos_dynamic_in_space(isl_space_copy(space));
 357         n_dynamic = n_dynamic_in_space(space);
 358         n_index = isl_aff_dim(aff, isl_dim_in) - n_dynamic;
 359
 360         isl_int_init(v);
 361
 362         for (int i = 0; i < pos_dynamic; ++i) {
 363                 if (!first)
 364                         os << ", ";
 365                 isl_aff_get_coefficient(aff, isl_dim_in, i, &v);
 366                 os << isl_int_get_si(v);
 367                 first = false;
 368         }
 369
 370         for (int i = pos_dynamic; i < n_index; ++i) {
 371                 if (!first)
 372                         os << ", ";
 373                 isl_aff_get_coefficient(aff, isl_dim_in, n_dynamic + i, &v);
 374                 os << isl_int_get_si(v);
 375                 first = false;
 376         }
 377
 378         for (int i = 0; i < n_dynamic; ++i) {
 379                 if (!first)
 380                         os << ", ";
 381                 isl_aff_get_coefficient(aff, isl_dim_in, pos_dynamic + i, &v);
 382                 os << isl_int_get_si(v);
 383                 first = false;
 384         }
 385
 386         for (int i = 0; i < isl_aff_dim(aff, isl_dim_param); ++i) {
 387                 if (!first)
 388                         os << ", ";
 389                 isl_aff_get_coefficient(aff, isl_dim_param, i, &v);
 390                 os << isl_int_get_si(v);
 391                 first = false;
 392         }
 393
 394         if (!first)
 395                 os << ", ";
 396         isl_aff_get_constant(aff, &v);
 397         os << isl_int_get_si(v);
 398
 399         isl_int_clear(v);
 400 }
 401
 402 /* Write out "map" in the form of a matrix, with each row
 403  * corresponding to an affine expression.
 404  */
 405 static void writeMatrix(xmlTextWriterPtr writer, const char *name,
 406         __isl_keep isl_multi_aff *map)
 407 {
 408         int rc;
 409         std::ostringstream strm;
 410         int n;
 411
 412         rc = xmlTextWriterStartElement(writer, BAD_CAST name);
 413         assert(rc >= 0);
 414
 415         strm << "[";
 416         n = isl_multi_aff_dim(map, isl_dim_out);
 417         for (int i = 0; i < n; ++i) {
 418                 isl_aff *aff;
 419                 if (i)
 420                         strm << "; ";
 421                 aff = isl_multi_aff_get_aff(map, i);
 422                 print_aff_coefficients(strm, aff);
 423                 isl_aff_free(aff);
 424         }
 425         strm << "]";
 426
 427         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "matrix",
 428                                          BAD_CAST strm.str().c_str());
 429         assert(rc >= 0);
 430
 431         rc = xmlTextWriterEndElement(writer);
 432         assert(rc >= 0);
 433 }
 434
 435 struct write_bound_data {
 436         xmlTextWriterPtr writer;
 437         adg_domain *domain;
 438         adg *graph;
 439 };
 440
 441 static int write_bound(__isl_take isl_basic_set *bset, void *user)
 442 {
 443         int rc;
 444         int nparam;
 445         std::ostringstream strm;
 446         write_bound_data *data = (write_bound_data *) user;
 447         xmlTextWriterPtr writer = data->writer;
 448
 449         rc = xmlTextWriterStartElement(writer, BAD_CAST "linearbound");
 450         assert(rc >= 0);
 451
 452         for (int i = 0; i < data->graph->iterators.size(); ++i) {
 453                 if (i)
 454                         strm << ", ";
 455                 strm << isl_id_get_name(data->graph->iterators[i]);
 456         }
 457
 458         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "index",
 459                                          BAD_CAST strm.str().c_str());
 460         assert(rc >= 0);
 461
 462         strm.str("");
 463         for (int i = 0; i < data->domain->controls.size(); ++i) {
 464                 if (i)
 465                         strm << ", ";
 466                 strm << isl_id_get_name(data->domain->controls[i]->name);
 467         }
 468         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "staticControl",
 469                                          BAD_CAST strm.str().c_str());
 470         assert(rc >= 0);
 471
 472         strm.str("");
 473         for (int i = 0; i < data->domain->filters.size(); ++i) {
 474                 if (i)
 475                         strm << ", ";
 476                 strm << data->domain->filters[i]->get_expr();
 477         }
 478         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "dynamicControl",
 479                                          BAD_CAST strm.str().c_str());
 480         assert(rc >= 0);
 481
 482         strm.str("");
 483         nparam = isl_basic_set_dim(bset, isl_dim_param);
 484         for (int i = 0; i < nparam; ++i) {
 485                 if (i)
 486                         strm << ", ";
 487                 strm << isl_basic_set_get_dim_name(bset, isl_dim_param, i);
 488         }
 489         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "parameter",
 490                                          BAD_CAST strm.str().c_str());
 491         assert(rc >= 0);
 492
 493         writeMatrix(writer, "constraint", bset, data->domain->filters.size());
 494
 495         isl_basic_set_free(bset);
 496
 497         if (data->graph->context &&
 498             !isl_set_plain_is_universe(data->graph->context)) {
 499                 assert(isl_set_n_basic_set(data->graph->context) == 1);
 500                 bset = isl_set_simple_hull(isl_set_copy(data->graph->context));
 501                 writeMatrix(writer, "context", bset, 0);
 502                 isl_basic_set_free(bset);
 503         }
 504
 505         for (int i = 0; i < data->domain->controls.size(); ++i)
 506                 writeExpr(writer, "control", "exp", data->domain->controls[i],
 507                             data->graph);
 508
 509         rc = xmlTextWriterEndElement(writer);
 510         assert(rc >= 0);
 511
 512         return 0;
 513 }
 514
 515 static void writeDomain(xmlTextWriterPtr writer, adg_domain *domain, adg *graph)
 516 {
 517         int rc;
 518         write_bound_data data = { writer, domain, graph };
 519
 520         rc = xmlTextWriterStartElement(writer, BAD_CAST "domain");
 521         assert(rc >= 0);
 522
 523         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "type",
 524                                                 BAD_CAST "LBS");
 525         assert(rc >= 0);
 526
 527         rc = isl_set_foreach_basic_set(domain->bounds, &write_bound, &data);
 528         assert(rc >= 0);
 529
 530         rc = xmlTextWriterEndElement(writer);
 531         assert(rc >= 0);
 532 }
 533
 534 static void writePort(xmlTextWriterPtr writer, adg_port *port, bool output,
 535         adg *graph)
 536 {
 537         int rc;
 538         const char *type;
 539
 540         type = output ? "outport" : "inport";
 541
 542         rc = xmlTextWriterStartElement(writer, BAD_CAST type);
 543         assert(rc >= 0);
 544
 545         assert(port->name);
 546         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 547                                          BAD_CAST isl_id_get_name(port->name));
 548         assert(port->node_name);
 549         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "node",
 550                                      BAD_CAST isl_id_get_name(port->node_name));
 551         assert(port->edge_name);
 552         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "edge",
 553                                      BAD_CAST isl_id_get_name(port->edge_name));
 554
 555         for (int i = 0; i < port->vars.size(); ++i)
 556                 writeVar(writer, "bindvariable", port->vars[i]);
 557
 558         writeDomain(writer, port->domain, graph);
 559
 560         rc = xmlTextWriterEndElement(writer);
 561         assert(rc >= 0);
 562 }
 563
 564 static void writeGate(xmlTextWriterPtr writer, adg_gate *gate, adg *graph)
 565 {
 566         int rc;
 567
 568         rc = xmlTextWriterStartElement(writer, BAD_CAST "invar");
 569         assert(rc >= 0);
 570
 571         assert(gate->name);
 572         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 573                                          BAD_CAST isl_id_get_name(gate->name));
 574
 575         assert(gate->in && gate->in->access);
 576         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "realName",
 577                                          BAD_CAST gate->in->get_expr());
 578
 579         assert(gate->out);
 580         writeVar(writer, "bindvariable", gate->out);
 581
 582         writeDomain(writer, gate->domain, graph);
 583
 584         rc = xmlTextWriterEndElement(writer);
 585         assert(rc >= 0);
 586 }
 587
 588 static void writeFunction(xmlTextWriterPtr writer, adg_function *fn, adg *graph)
 589 {
 590         int rc;
 591
 592         rc = xmlTextWriterStartElement(writer, BAD_CAST "function");
 593         assert(rc >= 0);
 594
 595         assert(fn->name);
 596         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 597                                          BAD_CAST isl_id_get_name(fn->name));
 598
 599         for (int i = 0; i < fn->in.size(); ++i)
 600                 writeArg(writer, "inargument", fn->in[i]);
 601         for (int i = 0; i < fn->out.size(); ++i)
 602                 writeArg(writer, "outargument", fn->out[i]);
 603         for (int i = 0; i < fn->ctrl.size(); ++i)
 604                 writeExpr(writer, "ctrlvar", "iterator", fn->ctrl[i], graph);
 605
 606         writeDomain(writer, fn->domain, graph);
 607
 608         rc = xmlTextWriterEndElement(writer);
 609         assert(rc >= 0);
 610 }
 611
 612 /* The gates should be printed after the input ports because
 613  * they may use data read through an input port.
 614  */
 615 static void writeNode(xmlTextWriterPtr writer, adg_node *node, adg *graph)
 616 {
 617         int rc;
 618
 619         rc = xmlTextWriterStartElement(writer, BAD_CAST "node");
 620         assert(rc >= 0);
 621
 622         assert(node->name);
 623         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 624                                          BAD_CAST isl_id_get_name(node->name));
 625         assert(rc >= 0);
 626         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "levelUpNode",
 627                                         BAD_CAST "");
 628         assert(rc >= 0);
 629
 630         for (int i = 0; i < node->input_ports.size(); ++i)
 631                 writePort(writer, node->input_ports[i], false, graph);
 632
 633         for (int i = 0; i < node->gates.size(); ++i)
 634                 writeGate(writer, node->gates[i], graph);
 635
 636         for (int i = 0; i < node->output_ports.size(); ++i)
 637                 writePort(writer, node->output_ports[i], true, graph);
 638
 639         for (int i = 0; i < node->expressions.size(); ++i)
 640                 writeExpr(writer, "expression", "value",
 641                                 node->expressions[i], graph);
 642
 643         writeFunction(writer, node->function, graph);
 644
 645         writeDomain(writer, node->domain, graph);
 646
 647         rc = xmlTextWriterEndElement(writer);
 648         assert(rc >= 0);
 649 }
 650
 651 static void writeEdge(xmlTextWriterPtr writer, adg_edge *edge)
 652 {
 653         int rc;
 654         std::ostringstream strm;
 655
 656         rc = xmlTextWriterStartElement(writer, BAD_CAST "edge");
 657         assert(rc >= 0);
 658
 659         assert(edge->name);
 660         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 661                                          BAD_CAST isl_id_get_name(edge->name));
 662         assert(rc >= 0);
 663
 664         assert(edge->from_port_name);
 665         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "fromPort",
 666                              BAD_CAST isl_id_get_name(edge->from_port_name));
 667         assert(rc >= 0);
 668
 669         assert(edge->from_node_name);
 670         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "fromNode",
 671                              BAD_CAST isl_id_get_name(edge->from_node_name));
 672         assert(rc >= 0);
 673
 674         assert(edge->to_port_name);
 675         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "toPort",
 676                              BAD_CAST isl_id_get_name(edge->to_port_name));
 677         assert(rc >= 0);
 678
 679         assert(edge->to_node_name);
 680         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "toNode",
 681                              BAD_CAST isl_id_get_name(edge->to_node_name));
 682         assert(rc >= 0);
 683
 684         strm << edge->value_size;
 685         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "size",
 686                                                  BAD_CAST strm.str().c_str());
 687         assert(rc >= 0);
 688
 689         rc = xmlTextWriterStartElement(writer, BAD_CAST "linearization");
 690         assert(rc >= 0);
 691
 692         switch (edge->type) {
 693         case adg_edge_fifo:
 694                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "type",
 695                                                  BAD_CAST "fifo");
 696                 break;
 697         case adg_edge_sticky_fifo:
 698                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "type",
 699                                                  BAD_CAST "sticky_fifo");
 700                 break;
 701         case adg_edge_shift_register:
 702                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "type",
 703                                                  BAD_CAST "shift_register");
 704                 break;
 705         case adg_edge_broadcast:
 706                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "type",
 707                                                  BAD_CAST "BroadcastInOrder");
 708                 break;
 709         case adg_edge_generic:
 710                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "type",
 711                                                  BAD_CAST "GenericOutOfOrder");
 712                 break;
 713         case adg_edge_error:
 714                 assert(0);
 715                 break;
 716         }
 717         assert(rc >= 0);
 718
 719         rc = xmlTextWriterEndElement(writer);
 720         assert(rc >= 0);
 721
 722         writeMatrix(writer, "mapping", edge->map);
 723
 724         rc = xmlTextWriterEndElement(writer);
 725         assert(rc >= 0);
 726 }
 727
 728 static void writeParam(xmlTextWriterPtr writer, adg_param *param, adg *graph)
 729 {
 730         int rc;
 731         std::ostringstream strm;
 732
 733         rc = xmlTextWriterStartElement(writer, BAD_CAST "parameter");
 734         assert(rc >= 0);
 735
 736         assert(param->name);
 737         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 738                                          BAD_CAST isl_id_get_name(param->name));
 739         assert(rc >= 0);
 740
 741         if (param->lb) {
 742                 strm.str("");
 743                 print_aff_expr(strm, param->lb);
 744                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "lb",
 745                                                  BAD_CAST strm.str().c_str());
 746                 assert(rc >= 0);
 747         }
 748
 749         if (param->ub) {
 750                 strm.str("");
 751                 print_aff_expr(strm, param->ub);
 752                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "ub",
 753                                                  BAD_CAST strm.str().c_str());
 754                 assert(rc >= 0);
 755         }
 756
 757         if (param->val) {
 758                 strm.str("");
 759                 print_aff_expr(strm, param->val);
 760                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "value",
 761                                                  BAD_CAST strm.str().c_str());
 762                 assert(rc >= 0);
 763         }
 764
 765         rc = xmlTextWriterEndElement(writer);
 766         assert(rc >= 0);
 767 }
 768
 769 static void writeADG(xmlTextWriterPtr writer, adg *graph)
 770 {
 771         int rc;
 772
 773         rc = xmlTextWriterStartElement(writer, BAD_CAST "adg");
 774         assert(rc >= 0);
 775
 776         assert(graph->name);
 777         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 778                                          BAD_CAST isl_id_get_name(graph->name));
 779         assert(rc >= 0);
 780         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "levelUpNode",
 781                                         BAD_CAST "");
 782         assert(rc >= 0);
 783
 784         for (int i = 0; i < graph->params.size(); ++i)
 785                 writeParam(writer, graph->params[i], graph);
 786
 787         for (int i = 0; i < graph->nodes.size(); ++i)
 788                 writeNode(writer, graph->nodes[i], graph);
 789
 790         for (int i = 0; i < graph->edges.size(); ++i)
 791                 writeEdge(writer, graph->edges[i]);
 792
 793         rc = xmlTextWriterEndElement(writer);
 794         assert(rc >= 0);
 795 }
 796
 797 /* Project out all the lifted variables that used to be
 798  * existentially quantified.  In other words, undo the lifting.
 799  * Also project out the dynamic control variables.
 800  */
 801 static __isl_give isl_set *unwrap(__isl_take isl_set *dom)
 802 {
 803         if (!isl_set_is_wrapping(dom))
 804                 return dom;
 805         return unwrap(isl_map_domain(isl_set_unwrap(dom)));
 806 }
 807
 808 /* Construct a schedule by adding an extra pair of dimensions to
 809  * domain->schedule, fixed to "offset1" and "offset2"
 810  * and setting the input name to "name".
 811  */
 812 static __isl_give isl_map *domain_schedule(adg_node *node, adg_domain *domain,
 813         int offset1, int offset2, __isl_take isl_id *name)
 814 {
 815         isl_set *dom;
 816         isl_map *sched;
 817         int n_out;
 818
 819         n_out = isl_map_dim(node->schedule, isl_dim_out);
 820
 821         dom = isl_set_copy(domain->bounds);
 822         dom = unwrap(dom);
 823
 824         sched = isl_map_copy(node->schedule);
 825         sched = isl_map_intersect_domain(sched, dom);
 826         sched = isl_map_add_dims(sched, isl_dim_out, 2);
 827         sched = isl_map_fix_si(sched, isl_dim_out, n_out, offset1);
 828         sched = isl_map_fix_si(sched, isl_dim_out, n_out + 1, offset2);
 829         sched = isl_map_set_tuple_id(sched, isl_dim_in, name);
 830
 831         return sched;
 832 }
 833
 834 static __isl_give isl_map *port_schedule(adg_node *node, adg_port *port,
 835         int offset)
 836 {
 837         return domain_schedule(node, port->domain, offset, port->arg_pos,
 838                                 isl_id_copy(port->name));
 839 }
 840
 841 static __isl_give isl_map *gate_schedule(adg_node *node, adg_gate *gate,
 842         int offset)
 843 {
 844         return domain_schedule(node, gate->domain, offset, 0,
 845                                 isl_id_copy(gate->name));
 846 }
 847
 848 /* Construct a schedule for all elements in the node.
 849  * We add an extra dimension to node->schedule to ensure that
 850  * the different elements are executed in the right order:
 851  * input ports, gates, function, output ports.
 852  * The input ports themselves are ordered according to the access nr.
 853  */
 854 static __isl_give isl_union_map *collect_node_schedule(adg_node *node, int n)
 855 {
 856         isl_map *sched_f;
 857         isl_union_map *sched;
 858         int n_out;
 859
 860         n_out = isl_map_dim(node->schedule, isl_dim_out);
 861
 862         sched_f = isl_map_copy(node->schedule);
 863         sched_f = isl_map_add_dims(sched_f, isl_dim_out, 2);
 864         sched_f = isl_map_fix_si(sched_f, isl_dim_out, n_out, 4 * n + 2);
 865         sched_f = isl_map_fix_si(sched_f, isl_dim_out, n_out + 1, 0);
 866
 867         sched = isl_union_map_from_map(sched_f);
 868
 869         for (int i = 0; i < node->input_ports.size(); ++i) {
 870                 isl_map *sched_p;
 871                 sched_p = port_schedule(node, node->input_ports[i], 4 * n + 0);
 872                 sched = isl_union_map_add_map(sched, sched_p);
 873         }
 874
 875         for (int i = 0; i < node->gates.size(); ++i) {
 876                 isl_map *sched_p;
 877                 sched_p = gate_schedule(node, node->gates[i], 4 * n + 1);
 878                 sched = isl_union_map_add_map(sched, sched_p);
 879         }
 880
 881         for (int i = 0; i < node->output_ports.size(); ++i) {
 882                 isl_map *sched_p;
 883                 sched_p = port_schedule(node, node->output_ports[i], 4 * n + 3);
 884                 sched = isl_union_map_add_map(sched, sched_p);
 885         }
 886
 887         return sched;
 888 }
 889
 890 /* Construct a schedule for all nodes in the graph.
 891  */
 892 static isl_union_map *collect_schedule(adg *graph)
 893 {
 894         isl_space *space = isl_set_get_space(graph->context);
 895         isl_union_map *sched = isl_union_map_empty(space);
 896
 897         for (int i = 0; i < graph->nodes.size(); ++i) {
 898                 isl_union_map *sched_i;
 899                 sched_i = collect_node_schedule(graph->nodes[i], i);
 900                 sched = isl_union_map_union(sched, sched_i);
 901         }
 902
 903         return sched;
 904 }
 905
 906 /* Construct a schedule, convert it to a clast using CLooG and then
 907  * write out the AST using writeAST.
 908  */
 909 static void writeAST(xmlTextWriterPtr writer, adg *graph)
 910 {
 911         int rc;
 912         isl_ctx *ctx = isl_set_get_ctx(graph->context);
 913         isl_union_map *sched;
 914         CloogState *cloog_state;
 915         CloogOptions *cloog_options;
 916         CloogDomain *context;
 917         CloogUnionDomain *ud;
 918         CloogInput *input;
 919
 920         sched = collect_schedule(graph);
 921
 922         cloog_state = cloog_isl_state_malloc(ctx);
 923         cloog_options = cloog_options_malloc(cloog_state);
 924         context = cloog_domain_from_isl_set(isl_set_copy(graph->context));
 925         ud = cloog_union_domain_from_isl_union_map(sched);
 926         for (int i = 0; i < graph->all_iterators.size(); ++i) {
 927                 const char *name = isl_id_get_name(graph->all_iterators[i]);
 928                 ud = cloog_union_domain_set_name(ud, CLOOG_SCAT, i, name);
 929         }
 930         input = cloog_input_alloc(context, ud);
 931         writeAST(writer, input, graph->all_iterators.size(), cloog_options);
 932         cloog_options_free(cloog_options);
 933         cloog_state_free(cloog_state);
 934 }
 935
 936 /* Write out an XML representation of "graph" to "out".
 937  * The adg part is obtained by scanning the data structure.
 938  * The ast part is obtained by running cloog based on the domain schedules.
 939  */
 940 void adg_print_xml(adg *graph, FILE *out)
 941 {
 942         int rc;
 943         xmlTextWriterPtr writer;
 944         xmlDocPtr doc;
 945
 946         LIBXML_TEST_VERSION
 947
 948         writer = xmlNewTextWriterDoc(&doc, 0);
 949         assert(writer);
 950
 951         rc = xmlTextWriterStartDocument(writer, NULL, NULL, NULL);
 952         assert(rc >= 0);
 953
 954         rc = xmlTextWriterStartDTD(writer, BAD_CAST "sadg",
 955                         BAD_CAST "-//LIACS//DTD ESPAM 1//EN",
 956                         BAD_CAST "http://www.liacs.nl/~cserc/dtd/espam_1.dtd");
 957         assert(rc >= 0);
 958         rc = xmlTextWriterEndDTD(writer);
 959         assert(rc >= 0);
 960
 961         rc = xmlTextWriterStartElement(writer, BAD_CAST "sadg");
 962         assert(rc >= 0);
 963
 964         writeADG(writer, graph);
 965         writeAST(writer, graph);
 966
 967         rc = xmlTextWriterEndElement(writer);
 968         assert(rc >= 0);
 969
 970         rc = xmlTextWriterEndDocument(writer);
 971         assert(rc >= 0);
 972
 973         xmlFreeTextWriter(writer);
 974
 975         rc = xmlDocFormatDump(out, doc, 1);
 976         assert(rc >= 0);
 977 }