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