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   std::map<isl_id *, tree>::iterator res;
 393   res = ip.find (id);
 394   if (ip.count (id))
 395     isl_id_free (res->first);
 396   ip[id] = iv;
 397   isl_ast_expr_free (for_iterator);
 398   return loop;
 399 }
 400
 401 static edge
 402 translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
 403                    edge next_e, ivs_params &ip);
 404
 405 /* Create the loop for a isl_ast_node_for.
 406
 407    - NEXT_E is the edge where new generated code should be attached.  */
 408
 409 static edge
 410 translate_isl_ast_for_loop (loop_p context_loop,
 411                             __isl_keep isl_ast_node *node_for, edge next_e,
 412                             tree type, tree lb, tree ub,
 413                             ivs_params &ip)
 414 {
 415   gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
 416   struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
 417                                                 type, lb, ub, ip);
 418   edge last_e = single_exit (loop);
 419   edge to_body = single_succ_edge (loop->header);
 420   basic_block after = to_body->dest;
 421
 422   /* Create a basic block for loop close phi nodes.  */
 423   last_e = single_succ_edge (split_edge (last_e));
 424
 425   /* Translate the body of the loop.  */
 426   isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
 427   next_e = translate_isl_ast (loop, for_body, to_body, ip);
 428   isl_ast_node_free (for_body);
 429   redirect_edge_succ_nodup (next_e, after);
 430   set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
 431
 432   /* TODO: Add checking for the loop parallelism.  */
 433
 434   return last_e;
 435 }
 436
 437 /* We use this function to get the upper bound because of the form,
 438    which is used by isl to represent loops:
 439
 440    for (iterator = init; cond; iterator += inc)
 441
 442    {
 443
 444      ...
 445
 446    }
 447
 448    The loop condition is an arbitrary expression, which contains the
 449    current loop iterator.
 450
 451    (e.g. iterator + 3 < B && C > iterator + A)
 452
 453    We have to know the upper bound of the iterator to generate a loop
 454    in Gimple form. It can be obtained from the special representation
 455    of the loop condition, which is generated by isl,
 456    if the ast_build_atomic_upper_bound option is set. In this case,
 457    isl generates a loop condition that consists of the current loop
 458    iterator, + an operator (< or <=) and an expression not involving
 459    the iterator, which is processed and returned by this function.
 460
 461    (e.g iterator <= upper-bound-expression-without-iterator)  */
 462
 463 static __isl_give isl_ast_expr *
 464 get_upper_bound (__isl_keep isl_ast_node *node_for)
 465 {
 466   gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
 467   isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
 468   gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
 469   isl_ast_expr *res;
 470   switch (isl_ast_expr_get_op_type (for_cond))
 471     {
 472     case isl_ast_op_le:
 473       res = isl_ast_expr_get_op_arg (for_cond, 1);
 474       break;
 475
 476     case isl_ast_op_lt:
 477       {
 478         // (iterator < ub) => (iterator <= ub - 1)
 479         isl_val *one =
 480           isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
 481         isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
 482         res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
 483         break;
 484       }
 485
 486     default:
 487       gcc_unreachable ();
 488     }
 489   isl_ast_expr_free (for_cond);
 490   return res;
 491 }
 492
 493 /* All loops generated by create_empty_loop_on_edge have the form of
 494    a post-test loop:
 495
 496    do
 497
 498    {
 499      body of the loop;
 500    } while (lower bound < upper bound);
 501
 502    We create a new if region protecting the loop to be executed, if
 503    the execution count is zero (lower bound > upper bound).  */
 504
 505 static edge
 506 graphite_create_new_loop_guard (edge entry_edge,
 507                                 __isl_keep isl_ast_node *node_for, tree *type,
 508                                 tree *lb, tree *ub, ivs_params &ip)
 509 {
 510   gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
 511   tree cond_expr;
 512   edge exit_edge;
 513
 514   *type =
 515     build_nonstandard_integer_type (graphite_expression_type_precision, 0);
 516   isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
 517   *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
 518   isl_ast_expr *upper_bound = get_upper_bound (node_for);
 519   *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip);
 520
 521   /* When ub is simply a constant or a parameter, use lb <= ub.  */
 522   if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
 523     cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
 524   else
 525     {
 526       tree one = (POINTER_TYPE_P (*type)
 527                   ? convert_to_ptrofftype (integer_one_node)
 528                   : fold_convert (*type, integer_one_node));
 529       /* Adding +1 and using LT_EXPR helps with loop latches that have a
 530          loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this
 531          becomes 2^k-1 due to integer overflow, and the condition lb <= ub
 532          is true, even if we do not want this.  However lb < ub + 1 is false,
 533          as expected.  */
 534       tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
 535                                  : PLUS_EXPR, *type, *ub, one);
 536
 537       cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
 538     }
 539
 540   exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
 541
 542   return exit_edge;
 543 }
 544
 545 /* Translates an isl_ast_node_for to Gimple. */
 546
 547 static edge
 548 translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node,
 549                             edge next_e, ivs_params &ip)
 550 {
 551   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for);
 552   tree type, lb, ub;
 553   edge last_e = graphite_create_new_loop_guard (next_e, node, &type,
 554                                                 &lb, &ub, ip);
 555   edge true_e = get_true_edge_from_guard_bb (next_e->dest);
 556
 557   translate_isl_ast_for_loop (context_loop, node, true_e,
 558                               type, lb, ub, ip);
 559   return last_e;
 560 }
 561
 562 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
 563    variables of the loops around GBB in SESE.
 564
 565    FIXME: Instead of using a vec<tree> that maps each loop id to a possible
 566    chrec, we could consider using a map<int, tree> that maps loop ids to the
 567    corresponding tree expressions.  */
 568
 569 static void
 570 build_iv_mapping (vec<tree> iv_map, gimple_bb_p gbb,
 571                   __isl_keep isl_ast_expr *user_expr, ivs_params &ip,
 572                   sese region)
 573 {
 574   gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op &&
 575               isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call);
 576   int i;
 577   isl_ast_expr *arg_expr;
 578   for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++)
 579     {
 580       arg_expr = isl_ast_expr_get_op_arg (user_expr, i);
 581       tree type =
 582         build_nonstandard_integer_type (graphite_expression_type_precision, 0);
 583       tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
 584       loop_p old_loop = gbb_loop_at_index (gbb, region, i - 1);
 585       iv_map[old_loop->num] = t;
 586     }
 587
 588 }
 589
 590 /* Translates an isl_ast_node_user to Gimple.
 591
 592    FIXME: We should remove iv_map.create (loop->num + 1), if it is possible.  */
 593
 594 static edge
 595 translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
 596                              edge next_e, ivs_params &ip)
 597 {
 598   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user);
 599   isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node);
 600   isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0);
 601   gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id);
 602   isl_id *name_id = isl_ast_expr_get_id (name_expr);
 603   poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id);
 604   gcc_assert (pbb);
 605   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
 606   vec<tree> iv_map;
 607   isl_ast_expr_free (name_expr);
 608   isl_id_free (name_id);
 609
 610   gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
 611               "The entry block should not even appear within a scop");
 612
 613   loop_p loop = gbb_loop (gbb);
 614   iv_map.create (loop->num + 1);
 615   iv_map.safe_grow_cleared (loop->num + 1);
 616
 617   build_iv_mapping (iv_map, gbb, user_expr, ip, SCOP_REGION (pbb->scop));
 618   isl_ast_expr_free (user_expr);
 619   next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb),
 620                                            SCOP_REGION (pbb->scop), next_e,
 621                                            iv_map,
 622                                            &graphite_regenerate_error);
 623   iv_map.release ();
 624   mark_virtual_operands_for_renaming (cfun);
 625   update_ssa (TODO_update_ssa);
 626   return next_e;
 627 }
 628
 629 /* Translates an isl_ast_node_block to Gimple. */
 630
 631 static edge
 632 translate_isl_ast_node_block (loop_p context_loop,
 633                               __isl_keep isl_ast_node *node,
 634                               edge next_e, ivs_params &ip)
 635 {
 636   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_block);
 637   isl_ast_node_list *node_list = isl_ast_node_block_get_children (node);
 638   int i;
 639   for (i = 0; i < isl_ast_node_list_n_ast_node (node_list); i++)
 640     {
 641       isl_ast_node *tmp_node = isl_ast_node_list_get_ast_node (node_list, i);
 642       next_e = translate_isl_ast (context_loop, tmp_node, next_e, ip);
 643       isl_ast_node_free (tmp_node);
 644     }
 645   isl_ast_node_list_free (node_list);
 646   return next_e;
 647 }
 648
 649 /* Translates an ISL AST node NODE to GCC representation in the
 650    context of a SESE.  */
 651
 652 static edge
 653 translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
 654                    edge next_e, ivs_params &ip)
 655 {
 656   switch (isl_ast_node_get_type (node))
 657     {
 658     case isl_ast_node_error:
 659       gcc_unreachable ();
 660
 661     case isl_ast_node_for:
 662       return translate_isl_ast_node_for (context_loop, node,
 663                                          next_e, ip);
 664
 665     case isl_ast_node_if:
 666       return next_e;
 667
 668     case isl_ast_node_user:
 669       return translate_isl_ast_node_user (node, next_e, ip);
 670
 671     case isl_ast_node_block:
 672       return translate_isl_ast_node_block (context_loop, node,
 673                                            next_e, ip);
 674
 675     default:
 676       gcc_unreachable ();
 677     }
 678 }
 679
 680 /* Prints NODE to FILE.  */
 681
 682 void
 683 print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node,
 684                     __isl_keep isl_ctx *ctx)
 685 {
 686   isl_printer *prn = isl_printer_to_file (ctx, file);
 687   prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
 688   prn = isl_printer_print_ast_node (prn, node);
 689   prn = isl_printer_print_str (prn, "\n");
 690   isl_printer_free (prn);
 691 }
 692
 693 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params  */
 694
 695 static void
 696 add_parameters_to_ivs_params (scop_p scop, ivs_params &ip)
 697 {
 698   sese region = SCOP_REGION (scop);
 699   unsigned nb_parameters = isl_set_dim (scop->context, isl_dim_param);
 700   gcc_assert (nb_parameters == SESE_PARAMS (region).length ());
 701   unsigned i;
 702   for (i = 0; i < nb_parameters; i++)
 703     {
 704       isl_id *tmp_id = isl_set_get_dim_id (scop->context, isl_dim_param, i);
 705       ip[tmp_id] = SESE_PARAMS (region)[i];
 706     }
 707 }
 708
 709
 710 /* Generates a build, which specifies the constraints on the parameters.  */
 711
 712 static __isl_give isl_ast_build *
 713 generate_isl_context (scop_p scop)
 714 {
 715   isl_set *context_isl = isl_set_params (isl_set_copy (scop->context));
 716   return isl_ast_build_from_context (context_isl);
 717 }
 718
 719 /* Get the maximal number of schedule dimensions in the scop SCOP.  */
 720
 721 static
 722 int get_max_schedule_dimensions (scop_p scop)
 723 {
 724   int i;
 725   poly_bb_p pbb;
 726   int schedule_dims = 0;
 727
 728   FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
 729     {
 730       int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out);
 731       if (pbb_schedule_dims > schedule_dims)
 732         schedule_dims = pbb_schedule_dims;
 733     }
 734
 735   return schedule_dims;
 736 }
 737
 738 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
 739
 740    For schedules with different dimensionality, the isl AST generator can not
 741    define an order and will just randomly choose an order. The solution to this
 742    problem is to extend all schedules to the maximal number of schedule
 743    dimensions (using '0's for the remaining values).  */
 744
 745 static __isl_give isl_map *
 746 extend_schedule (__isl_take isl_map *schedule, int nb_schedule_dims)
 747 {
 748   int tmp_dims = isl_map_dim (schedule, isl_dim_out);
 749   schedule =
 750     isl_map_add_dims (schedule, isl_dim_out, nb_schedule_dims - tmp_dims);
 751   isl_val *zero =
 752     isl_val_int_from_si (isl_map_get_ctx (schedule), 0);
 753   int i;
 754   for (i = tmp_dims; i < nb_schedule_dims; i++)
 755     {
 756       schedule =
 757         isl_map_fix_val (schedule, isl_dim_out, i, isl_val_copy (zero));
 758     }
 759   isl_val_free (zero);
 760   return schedule;
 761 }
 762
 763 /* Generates a schedule, which specifies an order used to
 764    visit elements in a domain.  */
 765
 766 static __isl_give isl_union_map *
 767 generate_isl_schedule (scop_p scop)
 768 {
 769   int nb_schedule_dims = get_max_schedule_dimensions (scop);
 770   int i;
 771   poly_bb_p pbb;
 772   isl_union_map *schedule_isl =
 773     isl_union_map_empty (isl_set_get_space (scop->context));
 774
 775   FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
 776     {
 777       /* Dead code elimination: when the domain of a PBB is empty,
 778          don't generate code for the PBB.  */
 779       if (isl_set_is_empty (pbb->domain))
 780         continue;
 781
 782       isl_map *bb_schedule = isl_map_copy (pbb->transformed);
 783       bb_schedule = isl_map_intersect_domain (bb_schedule,
 784                                               isl_set_copy (pbb->domain));
 785       bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims);
 786       schedule_isl =
 787         isl_union_map_union (schedule_isl,
 788                              isl_union_map_from_map (bb_schedule));
 789     }
 790   return schedule_isl;
 791 }
 792
 793 static __isl_give isl_ast_node *
 794 scop_to_isl_ast (scop_p scop, ivs_params &ip)
 795 {
 796   /* Generate loop upper bounds that consist of the current loop iterator,
 797   an operator (< or <=) and an expression not involving the iterator.
 798   If this option is not set, then the current loop iterator may appear several
 799   times in the upper bound. See the isl manual for more details.  */
 800   isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
 801
 802   add_parameters_to_ivs_params (scop, ip);
 803   isl_union_map *schedule_isl = generate_isl_schedule (scop);
 804   isl_ast_build *context_isl = generate_isl_context (scop);
 805   isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
 806                                                            schedule_isl);
 807   isl_ast_build_free (context_isl);
 808   return ast_isl;
 809 }
 810
 811 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
 812    the given SCOP.  Return true if code generation succeeded.
 813
 814    FIXME: This is not yet a full implementation of the code generator
 815           with ISL ASTs. Generation of GIMPLE code has to be completed.  */
 816
 817 bool
 818 graphite_regenerate_ast_isl (scop_p scop)
 819 {
 820   loop_p context_loop;
 821   sese region = SCOP_REGION (scop);
 822   ifsese if_region = NULL;
 823   isl_ast_node *root_node;
 824   ivs_params ip;
 825
 826   timevar_push (TV_GRAPHITE_CODE_GEN);
 827   graphite_regenerate_error = false;
 828   root_node = scop_to_isl_ast (scop, ip);
 829
 830   if (dump_file && (dump_flags & TDF_DETAILS))
 831     {
 832       fprintf (dump_file, "\nISL AST generated by ISL: \n");
 833       print_isl_ast_node (dump_file, root_node, scop->ctx);
 834       fprintf (dump_file, "\n");
 835     }
 836
 837   recompute_all_dominators ();
 838   graphite_verify ();
 839
 840   if_region = move_sese_in_condition (region);
 841   sese_insert_phis_for_liveouts (region,
 842                                  if_region->region->exit->src,
 843                                  if_region->false_region->exit,
 844                                  if_region->true_region->exit);
 845   recompute_all_dominators ();
 846   graphite_verify ();
 847
 848   context_loop = SESE_ENTRY (region)->src->loop_father;
 849
 850   translate_isl_ast (context_loop, root_node, if_region->true_region->entry,
 851                      ip);
 852   graphite_verify ();
 853   scev_reset ();
 854   recompute_all_dominators ();
 855   graphite_verify ();
 856
 857   if (graphite_regenerate_error)
 858     set_ifsese_condition (if_region, integer_zero_node);
 859
 860   free (if_region->true_region);
 861   free (if_region->region);
 862   free (if_region);
 863
 864   ivs_params_clear (ip);
 865   isl_ast_node_free (root_node);
 866   timevar_pop (TV_GRAPHITE_CODE_GEN);
 867   /* TODO: Add dump  */
 868   return !graphite_regenerate_error;
 869 }
 870 #endif