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