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_block to Gimple. */
 620
 621 static edge
 622 translate_isl_ast_node_block (loop_p context_loop,
 623                               __isl_keep isl_ast_node *node,
 624                               edge next_e, ivs_params &ip)
 625 {
 626   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_block);
 627   isl_ast_node_list *node_list = isl_ast_node_block_get_children (node);
 628   int i;
 629   for (i = 0; i < isl_ast_node_list_n_ast_node (node_list); i++)
 630     {
 631       isl_ast_node *tmp_node = isl_ast_node_list_get_ast_node (node_list, i);
 632       next_e = translate_isl_ast (context_loop, tmp_node, next_e, ip);
 633       isl_ast_node_free (tmp_node);
 634     }
 635   isl_ast_node_list_free (node_list);
 636   return next_e;
 637 }
 638
 639 /* Translates an ISL AST node NODE to GCC representation in the
 640    context of a SESE.  */
 641
 642 static edge
 643 translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
 644                    edge next_e, ivs_params &ip)
 645 {
 646   switch (isl_ast_node_get_type (node))
 647     {
 648     case isl_ast_node_error:
 649       gcc_unreachable ();
 650
 651     case isl_ast_node_for:
 652       return translate_isl_ast_node_for (context_loop, node,
 653                                          next_e, ip);
 654
 655     case isl_ast_node_if:
 656       return next_e;
 657
 658     case isl_ast_node_user:
 659       return translate_isl_ast_node_user (node, next_e, ip);
 660
 661     case isl_ast_node_block:
 662       return translate_isl_ast_node_block (context_loop, node,
 663                                            next_e, ip);
 664
 665     default:
 666       gcc_unreachable ();
 667     }
 668 }
 669
 670 /* Prints NODE to FILE.  */
 671
 672 void
 673 print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node,
 674                     __isl_keep isl_ctx *ctx)
 675 {
 676   isl_printer *prn = isl_printer_to_file (ctx, file);
 677   prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
 678   prn = isl_printer_print_ast_node (prn, node);
 679   prn = isl_printer_print_str (prn, "\n");
 680   isl_printer_free (prn);
 681 }
 682
 683 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params  */
 684
 685 static void
 686 add_parameters_to_ivs_params (scop_p scop, ivs_params &ip)
 687 {
 688   sese region = SCOP_REGION (scop);
 689   unsigned nb_parameters = isl_set_dim (scop->context, isl_dim_param);
 690   gcc_assert (nb_parameters == SESE_PARAMS (region).length ());
 691   unsigned i;
 692   for (i = 0; i < nb_parameters; i++)
 693     {
 694       isl_id *tmp_id = isl_set_get_dim_id (scop->context, isl_dim_param, i);
 695       ip[tmp_id] = SESE_PARAMS (region)[i];
 696     }
 697 }
 698
 699
 700 /* Generates a build, which specifies the constraints on the parameters.  */
 701
 702 static __isl_give isl_ast_build *
 703 generate_isl_context (scop_p scop)
 704 {
 705   isl_set *context_isl = isl_set_params (isl_set_copy (scop->context));
 706   return isl_ast_build_from_context (context_isl);
 707 }
 708
 709 /* Get the maximal number of schedule dimensions in the scop SCOP.  */
 710
 711 static
 712 int get_max_schedule_dimensions (scop_p scop)
 713 {
 714   int i;
 715   poly_bb_p pbb;
 716   int schedule_dims = 0;
 717
 718   FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
 719     {
 720       int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out);
 721       if (pbb_schedule_dims > schedule_dims)
 722         schedule_dims = pbb_schedule_dims;
 723     }
 724
 725   return schedule_dims;
 726 }
 727
 728 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
 729
 730    For schedules with different dimensionality, the isl AST generator can not
 731    define an order and will just randomly choose an order. The solution to this
 732    problem is to extend all schedules to the maximal number of schedule
 733    dimensions (using '0's for the remaining values).  */
 734
 735 static __isl_give isl_map *
 736 extend_schedule (__isl_take isl_map *schedule, int nb_schedule_dims)
 737 {
 738   int tmp_dims = isl_map_dim (schedule, isl_dim_out);
 739   schedule =
 740     isl_map_add_dims (schedule, isl_dim_out, nb_schedule_dims - tmp_dims);
 741   isl_val *zero =
 742     isl_val_int_from_si (isl_map_get_ctx (schedule), 0);
 743   int i;
 744   for (i = tmp_dims; i < nb_schedule_dims; i++)
 745     {
 746       schedule =
 747         isl_map_fix_val (schedule, isl_dim_out, i, isl_val_copy (zero));
 748     }
 749   isl_val_free (zero);
 750   return schedule;
 751 }
 752
 753 /* Generates a schedule, which specifies an order used to
 754    visit elements in a domain.  */
 755
 756 static __isl_give isl_union_map *
 757 generate_isl_schedule (scop_p scop)
 758 {
 759   int nb_schedule_dims = get_max_schedule_dimensions (scop);
 760   int i;
 761   poly_bb_p pbb;
 762   isl_union_map *schedule_isl =
 763     isl_union_map_empty (isl_set_get_space (scop->context));
 764
 765   FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
 766     {
 767       /* Dead code elimination: when the domain of a PBB is empty,
 768          don't generate code for the PBB.  */
 769       if (isl_set_is_empty (pbb->domain))
 770         continue;
 771
 772       isl_map *bb_schedule = isl_map_copy (pbb->transformed);
 773       bb_schedule = isl_map_intersect_domain (bb_schedule,
 774                                               isl_set_copy (pbb->domain));
 775       bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims);
 776       schedule_isl =
 777         isl_union_map_union (schedule_isl,
 778                              isl_union_map_from_map (bb_schedule));
 779     }
 780   return schedule_isl;
 781 }
 782
 783 static __isl_give isl_ast_node *
 784 scop_to_isl_ast (scop_p scop, ivs_params &ip)
 785 {
 786   /* Generate loop upper bounds that consist of the current loop iterator,
 787   an operator (< or <=) and an expression not involving the iterator.
 788   If this option is not set, then the current loop iterator may appear several
 789   times in the upper bound. See the isl manual for more details.  */
 790   isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
 791
 792   add_parameters_to_ivs_params (scop, ip);
 793   isl_union_map *schedule_isl = generate_isl_schedule (scop);
 794   isl_ast_build *context_isl = generate_isl_context (scop);
 795   isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
 796                                                            schedule_isl);
 797   isl_ast_build_free (context_isl);
 798   return ast_isl;
 799 }
 800
 801 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
 802    the given SCOP.  Return true if code generation succeeded.
 803
 804    FIXME: This is not yet a full implementation of the code generator
 805           with ISL ASTs. Generation of GIMPLE code has to be completed.  */
 806
 807 bool
 808 graphite_regenerate_ast_isl (scop_p scop)
 809 {
 810   loop_p context_loop;
 811   sese region = SCOP_REGION (scop);
 812   ifsese if_region = NULL;
 813   isl_ast_node *root_node;
 814   ivs_params ip;
 815
 816   timevar_push (TV_GRAPHITE_CODE_GEN);
 817   graphite_regenerate_error = false;
 818   root_node = scop_to_isl_ast (scop, ip);
 819
 820   if (dump_file && (dump_flags & TDF_DETAILS))
 821     {
 822       fprintf (dump_file, "\nISL AST generated by ISL: \n");
 823       print_isl_ast_node (dump_file, root_node, scop->ctx);
 824       fprintf (dump_file, "\n");
 825     }
 826
 827   recompute_all_dominators ();
 828   graphite_verify ();
 829
 830   if_region = move_sese_in_condition (region);
 831   sese_insert_phis_for_liveouts (region,
 832                                  if_region->region->exit->src,
 833                                  if_region->false_region->exit,
 834                                  if_region->true_region->exit);
 835   recompute_all_dominators ();
 836   graphite_verify ();
 837
 838   context_loop = SESE_ENTRY (region)->src->loop_father;
 839
 840   translate_isl_ast (context_loop, root_node, if_region->true_region->entry,
 841                      ip);
 842   graphite_verify ();
 843   scev_reset ();
 844   recompute_all_dominators ();
 845   graphite_verify ();
 846
 847   if (graphite_regenerate_error)
 848     set_ifsese_condition (if_region, integer_zero_node);
 849
 850   free (if_region->true_region);
 851   free (if_region->region);
 852   free (if_region);
 853
 854   ivs_params_clear (ip);
 855   isl_ast_node_free (root_node);
 856   timevar_pop (TV_GRAPHITE_CODE_GEN);
 857   /* TODO: Add dump  */
 858   return !graphite_regenerate_error;
 859 }
 860 #endif