xml_AST.cc

   1 #include <assert.h>
   2 #include <string.h>
   3 #include <sstream>
   4 #include <isl/id.h>
   5 #include <isl/val.h>
   6 #include <isl/aff.h>
   7 #include <isl/ast.h>
   8 #include "xml_AST.h"
   9
  10 using namespace std;
  11
  12 static void print_ast_expr_int(ostream &os, __isl_keep isl_ast_expr *expr)
  13 {
  14         isl_val *v;
  15
  16         v = isl_ast_expr_get_val(expr);
  17         os << isl_val_get_num_si(v);
  18         isl_val_free(v);
  19 }
  20
  21 static void print_ast_expr_id(ostream &os, __isl_keep isl_ast_expr *expr)
  22 {
  23         isl_id *id;
  24
  25         id = isl_ast_expr_get_id(expr);
  26         os << isl_id_get_name(id);
  27         isl_id_free(id);
  28 }
  29
  30 /* In ESPAM, the "div" and "mod" operators have the following meaning.
  31  *
  32  * int div(double a, double b) {
  33  *   return (int) (((a)<0) ? ((a)-(b)+1)/(b) : (a)/(b));
  34  * }
  35  * int mod(double a, double b) {
  36  *   return (int)fmod(a, b);
  37  * }
  38  *
  39  * That is, "div" rounds down, while "mod" rounds towards zero.
  40  */
  41 static const char *op_name(enum isl_ast_op_type type)
  42 {
  43         switch (type) {
  44         case isl_ast_op_add:
  45                 return " + ";
  46         case isl_ast_op_sub:
  47                 return " - ";
  48         case isl_ast_op_mul:
  49                 return " * ";
  50         case isl_ast_op_pdiv_q:
  51         case isl_ast_op_fdiv_q:
  52                 return "div";
  53         case isl_ast_op_pdiv_r:
  54         case isl_ast_op_zdiv_r:
  55                 return "mod";
  56         default:
  57                 assert(0);
  58         }
  59 }
  60
  61 static void print_ast_expr(ostream &os, __isl_keep isl_ast_expr *expr);
  62
  63 static void print_ast_expr_op(ostream &os, __isl_keep isl_ast_expr *expr)
  64 {
  65         enum isl_ast_op_type type;
  66         isl_ast_expr *arg;
  67
  68         type = isl_ast_expr_get_op_type(expr);
  69         switch (type) {
  70         case isl_ast_op_add:
  71         case isl_ast_op_sub:
  72         case isl_ast_op_mul:
  73                 arg = isl_ast_expr_get_op_arg(expr, 0);
  74                 print_ast_expr(os, arg);
  75                 isl_ast_expr_free(arg);
  76                 os << op_name(type);
  77                 arg = isl_ast_expr_get_op_arg(expr, 1);
  78                 print_ast_expr(os, arg);
  79                 isl_ast_expr_free(arg);
  80                 break;
  81         case isl_ast_op_pdiv_q:
  82         case isl_ast_op_pdiv_r:
  83         case isl_ast_op_fdiv_q:
  84         case isl_ast_op_zdiv_r:
  85                 os << op_name(type);
  86                 os << "(";
  87                 arg = isl_ast_expr_get_op_arg(expr, 0);
  88                 print_ast_expr(os, arg);
  89                 isl_ast_expr_free(arg);
  90                 os << ", ";
  91                 arg = isl_ast_expr_get_op_arg(expr, 1);
  92                 print_ast_expr(os, arg);
  93                 isl_ast_expr_free(arg);
  94                 os << ")";
  95                 break;
  96         default:
  97                 fprintf(stderr, "unhandled operation\n");
  98                 isl_ast_expr_dump(expr);
  99                 assert(0);
 100         }
 101 }
 102
 103 static void print_ast_expr(ostream &os, __isl_keep isl_ast_expr *expr)
 104 {
 105         enum isl_ast_expr_type type;
 106
 107         type = isl_ast_expr_get_type(expr);
 108         switch (type) {
 109         case isl_ast_expr_int:
 110                 print_ast_expr_int(os, expr);
 111                 break;
 112         case isl_ast_expr_id:
 113                 print_ast_expr_id(os, expr);
 114                 break;
 115         case isl_ast_expr_op:
 116                 print_ast_expr_op(os, expr);
 117                 break;
 118         case isl_ast_expr_error:
 119                 assert(0);
 120         }
 121 }
 122
 123 static string expr2string(__isl_keep isl_ast_expr *expr)
 124 {
 125         std::ostringstream strm;
 126
 127         print_ast_expr(strm, expr);
 128
 129         return strm.str();
 130 }
 131
 132 static void write_ast_node(xmlTextWriterPtr writer,
 133         __isl_keep isl_ast_node *block);
 134
 135 static bool is_max(__isl_keep isl_ast_expr *expr)
 136 {
 137         if (isl_ast_expr_get_type(expr) != isl_ast_expr_op)
 138                 return false;
 139         return isl_ast_expr_get_op_type(expr) == isl_ast_op_max;
 140 }
 141
 142 static bool is_min(__isl_keep isl_ast_expr *expr)
 143 {
 144         if (isl_ast_expr_get_type(expr) != isl_ast_expr_op)
 145                 return false;
 146         return isl_ast_expr_get_op_type(expr) == isl_ast_op_min;
 147 }
 148
 149 static __isl_give isl_ast_expr *extract_arg(__isl_take isl_ast_expr *expr,
 150         int pos)
 151 {
 152         isl_ast_expr *arg;
 153
 154         arg = isl_ast_expr_get_op_arg(expr, pos);
 155         isl_ast_expr_free(expr);
 156
 157         return arg;
 158 }
 159
 160 static bool is_comp(enum isl_ast_op_type type)
 161 {
 162         switch (type) {
 163         case isl_ast_op_eq:
 164         case isl_ast_op_le:
 165         case isl_ast_op_ge:
 166                 return true;
 167         default:
 168                 return false;
 169         }
 170 }
 171
 172 static const char *comp_sign(enum isl_ast_op_type type)
 173 {
 174         switch (type) {
 175         case isl_ast_op_eq:
 176                 return "0";
 177         case isl_ast_op_le:
 178                 return "-1";
 179         case isl_ast_op_ge:
 180                 return "1";
 181         default:
 182                 assert(0);
 183         }
 184 }
 185
 186 /* Write out the start of an if node representing the test
 187  *
 188  *      lhs == rhs      if sign is "0"
 189  *      lhs <= rhs      if sign is "-1" and strict is false
 190  *      lhs < rhs       if sign is "-1" and strict is true
 191  *      lhs >= rhs      if sign is "1"
 192  *
 193  * strict is only set by any of the callers when sign is "-1".
 194  * The end of the if node can be written out using write_ast_node_if_foot.
 195  */
 196 static void write_ast_node_if_head(xmlTextWriterPtr writer,
 197         __isl_keep isl_ast_expr *lhs, __isl_keep isl_ast_expr *rhs,
 198         const char *sign, bool strict = false)
 199 {
 200         int rc;
 201         string s;
 202
 203         rc = xmlTextWriterStartElement(writer, BAD_CAST "if");
 204         assert(rc >= 0);
 205
 206         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "LHS",
 207                                         BAD_CAST expr2string(lhs).c_str());
 208         assert(rc >= 0);
 209
 210         s = expr2string(rhs);
 211         if (strict)
 212                 s += " - 1";
 213         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "RHS",
 214                                         BAD_CAST s.c_str());
 215         assert(rc >= 0);
 216
 217         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "sign",
 218                                         BAD_CAST sign);
 219         assert(rc >= 0);
 220 }
 221
 222 static void write_ast_node_if_head(xmlTextWriterPtr writer,
 223         __isl_keep isl_ast_expr *expr)
 224 {
 225         int rc;
 226         isl_ast_expr *lhs, *rhs;
 227         enum isl_ast_op_type type;
 228         const char *sign;
 229
 230         lhs = isl_ast_expr_get_op_arg(expr, 0);
 231         rhs = isl_ast_expr_get_op_arg(expr, 1);
 232
 233         type = isl_ast_expr_get_op_type(expr);
 234         assert(is_comp(type));
 235         sign = comp_sign(type);
 236
 237         write_ast_node_if_head(writer, lhs, rhs, sign);
 238
 239         isl_ast_expr_free(lhs);
 240         isl_ast_expr_free(rhs);
 241 }
 242
 243 static void write_ast_node_if_foot(xmlTextWriterPtr writer)
 244 {
 245         int rc;
 246
 247         rc = xmlTextWriterEndElement(writer);
 248         assert(rc >= 0);
 249 }
 250
 251 /* Return a string representation of (part of) the upper bound
 252  * of the for node "node".
 253  *
 254  * If the upper bound is a non-zero constant, we return the empty string.
 255  * Otherwise, we assume it is a comparison, either "<=" (in which
 256  * case we set ub_strict to false) or "<" (in which case we set ub_strict
 257  * to true).
 258  * If the right-hand side is a min-expression, we set ub_min
 259  * and return a string representation of the first argument
 260  * of the min-expression.
 261  * Otherwise, we set ub_min to false and return a string representation
 262  * of the entire right-hand side.
 263  */
 264 static string ast_node_for_upper_bound(xmlTextWriterPtr writer,
 265         __isl_keep isl_ast_node *node, bool &ub_strict, bool &ub_min)
 266 {
 267         isl_ast_expr *expr;
 268         string ub;
 269         enum isl_ast_op_type type;
 270
 271         expr = isl_ast_node_for_get_cond(node);
 272
 273         if (isl_ast_expr_get_type(expr) == isl_ast_expr_int) {
 274                 isl_val *v;
 275                 v = isl_ast_expr_get_val(expr);
 276                 assert(!isl_val_is_zero(v));
 277                 isl_val_free(v);
 278                 isl_ast_expr_free(expr);
 279                 ub_strict = false;
 280                 ub_min = false;
 281                 return "";
 282         }
 283
 284         assert(isl_ast_expr_get_type(expr) == isl_ast_expr_op);
 285         type = isl_ast_expr_get_op_type(expr);
 286         assert(type == isl_ast_op_le || type == isl_ast_op_lt);
 287         ub_strict = type == isl_ast_op_lt;
 288         expr = extract_arg(expr, 1);
 289         ub_min = is_min(expr);
 290         if (ub_min)
 291                 expr = extract_arg(expr, 0);
 292         ub = expr2string(expr);
 293         if (ub_strict)
 294                 ub += " - 1";
 295         isl_ast_expr_free(expr);
 296
 297         return ub;
 298 }
 299
 300 /* Write out a for node.
 301  * ESPAM expects only a single expression for the lower and the upper
 302  * bound.  If these are a minimum/maximum of several expressions in "node",
 303  * then we only write out one of these expressions in the for node
 304  * and write out the others in nested if nodes.
 305  */
 306 static void write_ast_node_for(xmlTextWriterPtr writer,
 307         __isl_keep isl_ast_node *node)
 308 {
 309         int rc;
 310         isl_id *id;
 311         isl_ast_expr *expr, *it;
 312         isl_ast_node *body;
 313         string ub;
 314         bool lb_max, ub_strict, ub_min;
 315         int extra_foot = 0;
 316
 317         rc = xmlTextWriterStartElement(writer, BAD_CAST "for");
 318         assert(rc >= 0);
 319
 320         it = isl_ast_node_for_get_iterator(node);
 321         id = isl_ast_expr_get_id(it);
 322         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "iterator",
 323                                          BAD_CAST isl_id_get_name(id));
 324         isl_id_free(id);
 325         assert(rc >= 0);
 326
 327         expr = isl_ast_node_for_get_init(node);
 328         lb_max = is_max(expr);
 329         if (lb_max)
 330                 expr = extract_arg(expr, 0);
 331         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "LB",
 332                                          BAD_CAST expr2string(expr).c_str());
 333         assert(rc >= 0);
 334         isl_ast_expr_free(expr);
 335
 336         ub = ast_node_for_upper_bound(writer, node, ub_strict, ub_min);
 337         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "UB",
 338                                          BAD_CAST ub.c_str());
 339         assert(rc >= 0);
 340
 341         expr = isl_ast_node_for_get_inc(node);
 342         rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "stride",
 343                                          BAD_CAST expr2string(expr).c_str());
 344         assert(rc >= 0);
 345         isl_ast_expr_free(expr);
 346
 347         if (lb_max) {
 348                 int n;
 349                 expr = isl_ast_node_for_get_init(node);
 350                 n = isl_ast_expr_get_op_n_arg(expr) - 1;
 351                 extra_foot += n;
 352                 for (int i = 0; i < n; ++i) {
 353                         isl_ast_expr *arg;
 354                         arg = isl_ast_expr_get_op_arg(expr, 1 + i);
 355                         write_ast_node_if_head(writer, it, arg, "1");
 356                         isl_ast_expr_free(arg);
 357                 }
 358                 isl_ast_expr_free(expr);
 359         }
 360
 361         if (ub_min) {
 362                 int n;
 363                 expr = isl_ast_node_for_get_cond(node);
 364                 expr = extract_arg(expr, 1);
 365                 n = isl_ast_expr_get_op_n_arg(expr) - 1;
 366                 extra_foot += n;
 367                 for (int i = 0; i < n; ++i) {
 368                         isl_ast_expr *arg;
 369                         arg = isl_ast_expr_get_op_arg(expr, 1 + i);
 370                         write_ast_node_if_head(writer, it, arg, "-1",
 371                                                 ub_strict);
 372                         isl_ast_expr_free(arg);
 373                 }
 374                 isl_ast_expr_free(expr);
 375         }
 376
 377         body = isl_ast_node_for_get_body(node);
 378         write_ast_node(writer, body);
 379         isl_ast_node_free(body);
 380
 381         for (int i = 0; i < extra_foot; ++i)
 382                 write_ast_node_if_foot(writer);
 383
 384         rc = xmlTextWriterEndElement(writer);
 385         assert(rc >= 0);
 386
 387         isl_ast_expr_free(it);
 388 }
 389
 390 /* Write out the (conjunction of) condition(s) "cond"
 391  * as a sequence of heads of if nodes and return the number
 392  * of if nodes started.
 393  */
 394 static int write_ast_node_if_heads(xmlTextWriterPtr writer,
 395         __isl_take isl_ast_expr *cond)
 396 {
 397         int n;
 398         enum isl_ast_op_type type;
 399
 400         assert(isl_ast_expr_get_type(cond) == isl_ast_expr_op);
 401         type = isl_ast_expr_get_op_type(cond);
 402         if (is_comp(type)) {
 403                 write_ast_node_if_head(writer, cond);
 404                 n = 1;
 405         } else {
 406                 assert(type == isl_ast_op_and);
 407                 assert(isl_ast_expr_get_op_n_arg(cond) == 2);
 408                 n = 0;
 409                 for (int i = 0; i < 2; ++i) {
 410                         isl_ast_expr *arg;
 411
 412                         arg = isl_ast_expr_get_op_arg(cond, i);
 413                         n += write_ast_node_if_heads(writer, arg);
 414                 }
 415         }
 416         isl_ast_expr_free(cond);
 417
 418         return n;
 419 }
 420
 421 /* Write out an if node.
 422  * If "node" represents a conjunction of conditions, then an if node
 423  * is created for each of them.
 424  */
 425 static void write_ast_node_if(xmlTextWriterPtr writer,
 426         __isl_keep isl_ast_node *node)
 427 {
 428         int rc;
 429         int n;
 430         isl_ast_expr *cond;
 431         isl_ast_node *body;
 432
 433         cond = isl_ast_node_if_get_cond(node);
 434         n = write_ast_node_if_heads(writer, cond);
 435
 436         body = isl_ast_node_if_get_then(node);
 437         write_ast_node(writer, body);
 438         isl_ast_node_free(body);
 439
 440         for (int i = 0; i < n; ++i)
 441                 write_ast_node_if_foot(writer);
 442 }
 443
 444 static void write_ast_node_user(xmlTextWriterPtr writer,
 445         __isl_keep isl_ast_node *node)
 446 {
 447         int rc;
 448         isl_id *id;
 449         isl_ast_expr *expr, *arg;
 450         const char *name;
 451         const char *I;
 452
 453         expr = isl_ast_node_user_get_expr(node);
 454         arg = isl_ast_expr_get_op_arg(expr, 0);
 455         id = isl_ast_expr_get_id(arg);
 456         name = isl_id_get_name(id);
 457
 458         if ((I = strchr(name, 'I')) && I[1] == 'D') {
 459                 rc = xmlTextWriterStartElement(writer, BAD_CAST "var");
 460                 assert(rc >= 0);
 461
 462                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 463                                                 BAD_CAST name);
 464                 assert(rc >= 0);
 465         } else if (!strchr(name, 'P')) {
 466                 rc = xmlTextWriterStartElement(writer, BAD_CAST "stmt");
 467                 assert(rc >= 0);
 468
 469                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "node",
 470                                                 BAD_CAST name);
 471                 assert(rc >= 0);
 472         } else {
 473                 rc = xmlTextWriterStartElement(writer, BAD_CAST "port");
 474                 assert(rc >= 0);
 475
 476                 rc = xmlTextWriterWriteAttribute(writer, BAD_CAST "name",
 477                                                 BAD_CAST name);
 478                 assert(rc >= 0);
 479         }
 480
 481         rc = xmlTextWriterEndElement(writer);
 482         assert(rc >= 0);
 483
 484         isl_id_free(id);
 485         isl_ast_expr_free(arg);
 486         isl_ast_expr_free(expr);
 487 }
 488
 489 static void write_ast_node_block(xmlTextWriterPtr writer,
 490         __isl_keep isl_ast_node *block)
 491 {
 492         int n;
 493         isl_ast_node_list *list;
 494
 495         list = isl_ast_node_block_get_children(block);
 496         n = isl_ast_node_list_n_ast_node(list);
 497         for (int i = 0; i < n; ++i) {
 498                 isl_ast_node *node;
 499
 500                 node = isl_ast_node_list_get_ast_node(list, i);
 501                 write_ast_node(writer, node);
 502                 isl_ast_node_free(node);
 503         }
 504         isl_ast_node_list_free(list);
 505 }
 506
 507 static void write_ast_node(xmlTextWriterPtr writer,
 508         __isl_keep isl_ast_node *node)
 509 {
 510         enum isl_ast_node_type type;
 511
 512         type = isl_ast_node_get_type(node);
 513         switch (type) {
 514         case isl_ast_node_for:
 515                 write_ast_node_for(writer, node);
 516                 break;
 517         case isl_ast_node_if:
 518                 write_ast_node_if(writer, node);
 519                 break;
 520         case isl_ast_node_block:
 521                 write_ast_node_block(writer, node);
 522                 break;
 523         case isl_ast_node_user:
 524                 write_ast_node_user(writer, node);
 525                 break;
 526         case isl_ast_node_mark:
 527                 node = isl_ast_node_mark_get_node(node);
 528                 write_ast_node(writer, node);
 529                 isl_ast_node_free(node);
 530                 break;
 531         case isl_ast_node_error:
 532                 assert(0);
 533         }
 534 }
 535
 536 void writeAST(xmlTextWriterPtr writer, __isl_keep isl_ast_node *node)
 537 {
 538         int rc;
 539
 540         rc = xmlTextWriterStartElement(writer, BAD_CAST "ast");
 541         assert(rc >= 0);
 542
 543         write_ast_node(writer, node);
 544
 545         rc = xmlTextWriterEndElement(writer);
 546         assert(rc >= 0);
 547 }