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