gcc/graphite-isl-ast-to-gimple.c

   1 /* Translation of ISL AST to Gimple.
   2    Copyright (C) 2014 Free Software Foundation, Inc.
   3    Contributed by Roman Gareev <gareevroman@gmail.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22
  23 #ifdef HAVE_cloog
  24 #include <isl/set.h>
  25 #include <isl/map.h>
  26 #include <isl/union_map.h>
  27 #include <isl/ast_build.h>
  28 #if defined(__cplusplus)
  29 extern "C" {
  30 #endif
  31 #include <isl/val_gmp.h>
  32 #if defined(__cplusplus)
  33 }
  34 #endif
  35 #endif
  36
  37 #include "system.h"
  38 #include "coretypes.h"
  39 #include "tree.h"
  40 #include "basic-block.h"
  41 #include "tree-ssa-alias.h"
  42 #include "internal-fn.h"
  43 #include "gimple-expr.h"
  44 #include "is-a.h"
  45 #include "gimple.h"
  46 #include "gimple-iterator.h"
  47 #include "tree-ssa-loop.h"
  48 #include "tree-pass.h"
  49 #include "cfgloop.h"
  50 #include "tree-data-ref.h"
  51 #include "sese.h"
  52 #include "tree-ssa-loop-manip.h"
  53 #include "tree-scalar-evolution.h"
  54 #include <map>
  55
  56 #ifdef HAVE_cloog
  57 #include "graphite-poly.h"
  58 #include "graphite-isl-ast-to-gimple.h"
  59
  60 /* This flag is set when an error occurred during the translation of
  61    ISL AST to Gimple.  */
  62
  63 static bool graphite_regenerate_error;
  64
  65 /* We always use signed 128, until isl is able to give information about
  66 types  */
  67
  68 static tree *graphite_expression_size_type = &int128_integer_type_node;
  69
  70 /* Converts a GMP constant VAL to a tree and returns it.  */
  71
  72 static tree
  73 gmp_cst_to_tree (tree type, mpz_t val)
  74 {
  75   tree t = type ? type : integer_type_node;
  76   mpz_t tmp;
  77
  78   mpz_init (tmp);
  79   mpz_set (tmp, val);
  80   wide_int wi = wi::from_mpz (t, tmp, true);
  81   mpz_clear (tmp);
  82
  83   return wide_int_to_tree (t, wi);
  84 }
  85
  86 /* Verifies properties that GRAPHITE should maintain during translation.  */
  87
  88 static inline void
  89 graphite_verify (void)
  90 {
  91 #ifdef ENABLE_CHECKING
  92   verify_loop_structure ();
  93   verify_loop_closed_ssa (true);
  94 #endif
  95 }
  96
  97 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
  98    to corresponding trees.  */
  99
 100 typedef std::map<isl_id *, tree> ivs_params;
 101
 102 /* Free all memory allocated for ISL's identifiers.  */
 103
 104 void ivs_params_clear (ivs_params &ip)
 105 {
 106   std::map<isl_id *, tree>::iterator it;
 107   for (it = ip.begin ();
 108        it != ip.end (); it++)
 109     {
 110       isl_id_free (it->first);
 111     }
 112 }
 113
 114 static tree
 115 gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *,
 116                                     ivs_params &ip);
 117
 118 /* Return the tree variable that corresponds to the given isl ast identifier
 119  expression (an isl_ast_expr of type isl_ast_expr_id).  */
 120
 121 static tree
 122 gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id,
 123                                      ivs_params &ip)
 124 {
 125   gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
 126   isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
 127   std::map<isl_id *, tree>::iterator res;
 128   res = ip.find (tmp_isl_id);
 129   isl_id_free (tmp_isl_id);
 130   gcc_assert (res != ip.end () &&
 131               "Could not map isl_id to tree expression");
 132   isl_ast_expr_free (expr_id);
 133   return res->second;
 134 }
 135
 136 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
 137    type TYPE.  */
 138
 139 static tree
 140 gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr)
 141 {
 142   gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
 143   isl_val *val = isl_ast_expr_get_val (expr);
 144   mpz_t val_mpz_t;
 145   mpz_init (val_mpz_t);
 146   tree res;
 147   if (isl_val_get_num_gmp (val, val_mpz_t) == -1)
 148     res = NULL_TREE;
 149   else
 150     res = gmp_cst_to_tree (type, val_mpz_t);
 151   isl_val_free (val);
 152   isl_ast_expr_free (expr);
 153   mpz_clear (val_mpz_t);
 154   return res;
 155 }
 156
 157 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
 158    type TYPE.  */
 159
 160 static tree
 161 binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
 162 {
 163   isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
 164   tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
 165   arg_expr = isl_ast_expr_get_op_arg (expr, 1);
 166   tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
 167   enum isl_ast_op_type expr_type = isl_ast_expr_get_op_type (expr);
 168   isl_ast_expr_free (expr);
 169   switch (expr_type)
 170     {
 171     case isl_ast_op_add:
 172       return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 173
 174     case isl_ast_op_sub:
 175       return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 176
 177     case isl_ast_op_mul:
 178       return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 179
 180     case isl_ast_op_div:
 181       return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 182
 183     case isl_ast_op_fdiv_q:
 184       return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 185
 186     case isl_ast_op_and:
 187       return fold_build2 (TRUTH_ANDIF_EXPR, type,
 188                           tree_lhs_expr, tree_rhs_expr);
 189
 190     case isl_ast_op_or:
 191       return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 192
 193     case isl_ast_op_eq:
 194       return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 195
 196     case isl_ast_op_le:
 197       return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 198
 199     case isl_ast_op_lt:
 200       return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 201
 202     case isl_ast_op_ge:
 203       return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 204
 205     case isl_ast_op_gt:
 206       return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 207
 208     default:
 209       gcc_unreachable ();
 210     }
 211 }
 212
 213 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
 214    type TYPE.  */
 215
 216 static tree
 217 ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
 218 {
 219   gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
 220   isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
 221   tree tree_first_expr
 222     = gcc_expression_from_isl_expression (type, arg_expr, ip);
 223   arg_expr = isl_ast_expr_get_op_arg (expr, 1);
 224   tree tree_second_expr
 225     = gcc_expression_from_isl_expression (type, arg_expr, ip);
 226   arg_expr = isl_ast_expr_get_op_arg (expr, 2);
 227   tree tree_third_expr
 228     = gcc_expression_from_isl_expression (type, arg_expr, ip);
 229   isl_ast_expr_free (expr);
 230   return fold_build3 (COND_EXPR, type, tree_first_expr,
 231                       tree_second_expr, tree_third_expr);
 232 }
 233
 234 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
 235    type TYPE.  */
 236
 237 static tree
 238 unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
 239 {
 240   gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
 241   isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
 242   tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
 243   isl_ast_expr_free (expr);
 244   return fold_build1 (NEGATE_EXPR, type, tree_expr);
 245 }
 246
 247 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
 248    to a GCC expression tree of type TYPE.  */
 249
 250 static tree
 251 nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
 252 {
 253   enum tree_code op_code;
 254   switch (isl_ast_expr_get_op_type (expr))
 255     {
 256     case isl_ast_op_max:
 257       op_code = MAX_EXPR;
 258       break;
 259
 260     case isl_ast_op_min:
 261       op_code = MIN_EXPR;
 262       break;
 263
 264     default:
 265       gcc_unreachable ();
 266     }
 267   isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
 268   tree res = gcc_expression_from_isl_expression (type, arg_expr, ip);
 269   int i;
 270   for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
 271     {
 272       arg_expr = isl_ast_expr_get_op_arg (expr, i);
 273       tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
 274       res = fold_build2 (op_code, type, res, t);
 275     }
 276   isl_ast_expr_free (expr);
 277   return res;
 278 }
 279
 280
 281 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
 282    type TYPE.  */
 283
 284 static tree
 285 gcc_expression_from_isl_expr_op (tree type, __isl_take isl_ast_expr *expr,
 286                                  ivs_params &ip)
 287 {
 288   gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
 289   switch (isl_ast_expr_get_op_type (expr))
 290     {
 291     /* These isl ast expressions are not supported yet.  */
 292     case isl_ast_op_error:
 293     case isl_ast_op_call:
 294     case isl_ast_op_and_then:
 295     case isl_ast_op_or_else:
 296     case isl_ast_op_pdiv_q:
 297     case isl_ast_op_pdiv_r:
 298     case isl_ast_op_select:
 299       gcc_unreachable ();
 300
 301     case isl_ast_op_max:
 302     case isl_ast_op_min:
 303       return nary_op_to_tree (type, expr, ip);
 304
 305     case isl_ast_op_add:
 306     case isl_ast_op_sub:
 307     case isl_ast_op_mul:
 308     case isl_ast_op_div:
 309     case isl_ast_op_fdiv_q:
 310     case isl_ast_op_and:
 311     case isl_ast_op_or:
 312     case isl_ast_op_eq:
 313     case isl_ast_op_le:
 314     case isl_ast_op_lt:
 315     case isl_ast_op_ge:
 316     case isl_ast_op_gt:
 317       return binary_op_to_tree (type, expr, ip);
 318
 319     case isl_ast_op_minus:
 320       return unary_op_to_tree (type, expr, ip);
 321
 322     case isl_ast_op_cond:
 323       return ternary_op_to_tree (type, expr, ip);
 324
 325     default:
 326       gcc_unreachable ();
 327     }
 328
 329   return NULL_TREE;
 330 }
 331
 332 /* Converts an ISL AST expression E back to a GCC expression tree of
 333    type TYPE.  */
 334
 335 static tree
 336 gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *expr,
 337                                     ivs_params &ip)
 338 {
 339   switch (isl_ast_expr_get_type (expr))
 340     {
 341     case isl_ast_expr_id:
 342       return gcc_expression_from_isl_ast_expr_id (expr, ip);
 343
 344     case isl_ast_expr_int:
 345       return gcc_expression_from_isl_expr_int (type, expr);
 346
 347     case isl_ast_expr_op:
 348       return gcc_expression_from_isl_expr_op (type, expr, ip);
 349
 350     default:
 351       gcc_unreachable ();
 352     }
 353
 354   return NULL_TREE;
 355 }
 356
 357 /* Creates a new LOOP corresponding to isl_ast_node_for.  Inserts an
 358    induction variable for the new LOOP.  New LOOP is attached to CFG
 359    starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
 360    becomes the child loop of the OUTER_LOOP.  NEWIVS_INDEX binds
 361    ISL's scattering name to the induction variable created for the
 362    loop of STMT.  The new induction variable is inserted in the NEWIVS
 363    vector and is of type TYPE.  */
 364
 365 static struct loop *
 366 graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for,
 367                           loop_p outer, tree type, tree lb, tree ub,
 368                           ivs_params &ip)
 369 {
 370   isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
 371   tree stride = gcc_expression_from_isl_expression (type, for_inc, ip);
 372   tree ivvar = create_tmp_var (type, "graphite_IV");
 373   tree iv, iv_after_increment;
 374   loop_p loop = create_empty_loop_on_edge
 375     (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
 376      outer ? outer : entry_edge->src->loop_father);
 377
 378   isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
 379   isl_id *id = isl_ast_expr_get_id (for_iterator);
 380   ip[id] = iv;
 381   isl_ast_expr_free (for_iterator);
 382   return loop;
 383 }
 384
 385 static edge
 386 translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
 387                    edge next_e, ivs_params &ip);
 388
 389 /* Create the loop for a isl_ast_node_for.
 390
 391    - NEXT_E is the edge where new generated code should be attached.  */
 392
 393 static edge
 394 translate_isl_ast_for_loop (loop_p context_loop,
 395                             __isl_keep isl_ast_node *node_for, edge next_e,
 396                             tree type, tree lb, tree ub,
 397                             ivs_params &ip)
 398 {
 399   gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
 400   struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
 401                                                 type, lb, ub, ip);
 402   edge last_e = single_exit (loop);
 403   edge to_body = single_succ_edge (loop->header);
 404   basic_block after = to_body->dest;
 405
 406   /* Create a basic block for loop close phi nodes.  */
 407   last_e = single_succ_edge (split_edge (last_e));
 408
 409   /* Translate the body of the loop.  */
 410   isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
 411   next_e = translate_isl_ast (loop, for_body, to_body, ip);
 412   isl_ast_node_free (for_body);
 413   redirect_edge_succ_nodup (next_e, after);
 414   set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
 415
 416   /* TODO: Add checking for the loop parallelism.  */
 417
 418   return last_e;
 419 }
 420
 421 /* We use this function to get the upper bound because of the form,
 422    which is used by isl to represent loops:
 423
 424    for (iterator = init; cond; iterator += inc)
 425
 426    {
 427
 428      ...
 429
 430    }
 431
 432    The loop condition is an arbitrary expression, which contains the
 433    current loop iterator.
 434
 435    (e.g. iterator + 3 < B && C > iterator + A)
 436
 437    We have to know the upper bound of the iterator to generate a loop
 438    in Gimple form. It can be obtained from the special representation
 439    of the loop condition, which is generated by isl,
 440    if the ast_build_atomic_upper_bound option is set. In this case,
 441    isl generates a loop condition that consists of the current loop
 442    iterator, + an operator (< or <=) and an expression not involving
 443    the iterator, which is processed and returned by this function.
 444
 445    (e.g iterator <= upper-bound-expression-without-iterator)  */
 446
 447 static __isl_give isl_ast_expr *
 448 get_upper_bound (__isl_keep isl_ast_node *node_for)
 449 {
 450   gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
 451   isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
 452   gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
 453   isl_ast_expr *res;
 454   switch (isl_ast_expr_get_op_type (for_cond))
 455     {
 456     case isl_ast_op_le:
 457       res = isl_ast_expr_get_op_arg (for_cond, 1);
 458       break;
 459
 460     case isl_ast_op_lt:
 461       {
 462         // (iterator < ub) => (iterator <= ub - 1)
 463         isl_val *one = isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
 464         isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
 465         res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
 466         break;
 467       }
 468
 469     default:
 470       gcc_unreachable ();
 471     }
 472   isl_ast_expr_free (for_cond);
 473   return res;
 474 }
 475
 476 /* All loops generated by create_empty_loop_on_edge have the form of
 477    a post-test loop:
 478
 479    do
 480
 481    {
 482      body of the loop;
 483    } while (lower bound < upper bound);
 484
 485    We create a new if region protecting the loop to be executed, if
 486    the execution count is zero (lower bound > upper bound).  */
 487
 488 static edge
 489 graphite_create_new_loop_guard (edge entry_edge,
 490                                 __isl_keep isl_ast_node *node_for, tree *type,
 491                                 tree *lb, tree *ub, ivs_params &ip)
 492 {
 493   gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
 494   tree cond_expr;
 495   edge exit_edge;
 496
 497   *type = *graphite_expression_size_type;
 498   isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
 499   *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
 500   isl_ast_expr *upper_bound = get_upper_bound (node_for);
 501   *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip);
 502
 503   /* When ub is simply a constant or a parameter, use lb <= ub.  */
 504   if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
 505     cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
 506   else
 507     {
 508       tree one = (POINTER_TYPE_P (*type)
 509                   ? convert_to_ptrofftype (integer_one_node)
 510                   : fold_convert (*type, integer_one_node));
 511       /* Adding +1 and using LT_EXPR helps with loop latches that have a
 512          loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this
 513          becomes 2^k-1 due to integer overflow, and the condition lb <= ub
 514          is true, even if we do not want this.  However lb < ub + 1 is false,
 515          as expected.  */
 516       tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
 517                                  : PLUS_EXPR, *type, *ub, one);
 518
 519       cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
 520     }
 521
 522   exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
 523
 524   return exit_edge;
 525 }
 526
 527 /* Translates an isl_ast_node_for to Gimple. */
 528
 529 static edge
 530 translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node,
 531                             edge next_e, ivs_params &ip)
 532 {
 533   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for);
 534   tree type, lb, ub;
 535   edge last_e = graphite_create_new_loop_guard (next_e, node, &type,
 536                                                 &lb, &ub, ip);
 537   edge true_e = get_true_edge_from_guard_bb (next_e->dest);
 538
 539   translate_isl_ast_for_loop (context_loop, node, true_e,
 540                               type, lb, ub, ip);
 541   return last_e;
 542 }
 543
 544 /* Translates an ISL AST node NODE to GCC representation in the
 545    context of a SESE.  */
 546
 547 static edge
 548 translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
 549                    edge next_e, ivs_params &ip)
 550 {
 551   switch (isl_ast_node_get_type (node))
 552     {
 553     case isl_ast_node_error:
 554       gcc_unreachable ();
 555
 556     case isl_ast_node_for:
 557       return translate_isl_ast_node_for (context_loop, node,
 558                                          next_e, ip);
 559
 560     case isl_ast_node_if:
 561       return next_e;
 562
 563     case isl_ast_node_user:
 564       return next_e;
 565
 566     case isl_ast_node_block:
 567       return next_e;
 568
 569     default:
 570       gcc_unreachable ();
 571     }
 572 }
 573
 574 /* Prints NODE to FILE.  */
 575
 576 void
 577 print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node,
 578                     __isl_keep isl_ctx *ctx)
 579 {
 580   isl_printer *prn = isl_printer_to_file (ctx, file);
 581   prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
 582   prn = isl_printer_print_ast_node (prn, node);
 583   prn = isl_printer_print_str (prn, "\n");
 584   isl_printer_free (prn);
 585 }
 586
 587 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params  */
 588
 589 static void
 590 add_parameters_to_ivs_params (scop_p scop, ivs_params &ip)
 591 {
 592   sese region = SCOP_REGION (scop);
 593   unsigned nb_parameters = isl_set_dim (scop->context, isl_dim_param);
 594   gcc_assert (nb_parameters == SESE_PARAMS (region).length ());
 595   unsigned i;
 596   for (i = 0; i < nb_parameters; i++)
 597     {
 598       isl_id *tmp_id = isl_set_get_dim_id (scop->context, isl_dim_param, i);
 599       ip[tmp_id] = SESE_PARAMS (region)[i];
 600     }
 601 }
 602
 603
 604 /* Generates a build, which specifies the constraints on the parameters.  */
 605
 606 static __isl_give isl_ast_build *
 607 generate_isl_context (scop_p scop)
 608 {
 609   isl_set *context_isl = isl_set_params (isl_set_copy (scop->context));
 610   return isl_ast_build_from_context (context_isl);
 611 }
 612
 613 /* Generates a schedule, which specifies an order used to
 614    visit elements in a domain.  */
 615
 616 static __isl_give isl_union_map *
 617 generate_isl_schedule (scop_p scop)
 618 {
 619   int i;
 620   poly_bb_p pbb;
 621   isl_union_map *schedule_isl =
 622     isl_union_map_empty (isl_set_get_space (scop->context));
 623
 624   FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
 625     {
 626       /* Dead code elimination: when the domain of a PBB is empty,
 627          don't generate code for the PBB.  */
 628       if (isl_set_is_empty (pbb->domain))
 629         continue;
 630
 631       isl_map *bb_schedule = isl_map_copy (pbb->transformed);
 632       bb_schedule = isl_map_intersect_domain (bb_schedule,
 633                                               isl_set_copy (pbb->domain));
 634       schedule_isl =
 635         isl_union_map_union (schedule_isl,
 636                              isl_union_map_from_map (bb_schedule));
 637     }
 638   return schedule_isl;
 639 }
 640
 641 static __isl_give isl_ast_node *
 642 scop_to_isl_ast (scop_p scop, ivs_params &ip)
 643 {
 644   /* Generate loop upper bounds that consist of the current loop iterator,
 645   an operator (< or <=) and an expression not involving the iterator.
 646   If this option is not set, then the current loop iterator may appear several
 647   times in the upper bound. See the isl manual for more details.  */
 648   isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
 649
 650   add_parameters_to_ivs_params (scop, ip);
 651   isl_union_map *schedule_isl = generate_isl_schedule (scop);
 652   isl_ast_build *context_isl = generate_isl_context (scop);
 653   isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
 654                                                            schedule_isl);
 655   isl_ast_build_free (context_isl);
 656   return ast_isl;
 657 }
 658
 659 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
 660    the given SCOP.  Return true if code generation succeeded.
 661
 662    FIXME: This is not yet a full implementation of the code generator
 663           with ISL ASTs. Generation of GIMPLE code has to be completed.  */
 664
 665 bool
 666 graphite_regenerate_ast_isl (scop_p scop)
 667 {
 668   loop_p context_loop;
 669   sese region = SCOP_REGION (scop);
 670   ifsese if_region = NULL;
 671   isl_ast_node *root_node;
 672   ivs_params ip;
 673
 674   timevar_push (TV_GRAPHITE_CODE_GEN);
 675   graphite_regenerate_error = false;
 676   root_node = scop_to_isl_ast (scop, ip);
 677
 678   if (dump_file && (dump_flags & TDF_DETAILS))
 679     {
 680       fprintf (dump_file, "\nISL AST generated by ISL: \n");
 681       print_isl_ast_node (dump_file, root_node, scop->ctx);
 682       fprintf (dump_file, "\n");
 683     }
 684
 685   recompute_all_dominators ();
 686   graphite_verify ();
 687
 688   if_region = move_sese_in_condition (region);
 689   sese_insert_phis_for_liveouts (region,
 690                                  if_region->region->exit->src,
 691                                  if_region->false_region->exit,
 692                                  if_region->true_region->exit);
 693   recompute_all_dominators ();
 694   graphite_verify ();
 695
 696   context_loop = SESE_ENTRY (region)->src->loop_father;
 697
 698   translate_isl_ast (context_loop, root_node, if_region->true_region->entry,
 699                      ip);
 700   graphite_verify ();
 701   scev_reset ();
 702   recompute_all_dominators ();
 703   graphite_verify ();
 704
 705   if (graphite_regenerate_error)
 706     set_ifsese_condition (if_region, integer_zero_node);
 707
 708   free (if_region->true_region);
 709   free (if_region->region);
 710   free (if_region);
 711
 712   ivs_params_clear (ip);
 713   isl_ast_node_free (root_node);
 714   timevar_pop (TV_GRAPHITE_CODE_GEN);
 715   /* TODO: Add dump  */
 716   return !graphite_regenerate_error;
 717 }
 718 #endif