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