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_isl
  24 #include <isl/set.h>
  25 #include <isl/map.h>
  26 #include <isl/union_map.h>
  27 #include <isl/ast_build.h>
  28
  29 /* Since ISL-0.13, the extern is in val_gmp.h.  */
  30 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
  31 extern "C" {
  32 #endif
  33 #include <isl/val_gmp.h>
  34 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
  35 }
  36 #endif
  37 #endif
  38
  39 #include "system.h"
  40 #include "coretypes.h"
  41 #include "tree.h"
  42 #include "predict.h"
  43 #include "vec.h"
  44 #include "hashtab.h"
  45 #include "hash-set.h"
  46 #include "machmode.h"
  47 #include "tm.h"
  48 #include "hard-reg-set.h"
  49 #include "input.h"
  50 #include "function.h"
  51 #include "dominance.h"
  52 #include "cfg.h"
  53 #include "basic-block.h"
  54 #include "tree-ssa-alias.h"
  55 #include "internal-fn.h"
  56 #include "gimple-expr.h"
  57 #include "is-a.h"
  58 #include "gimple.h"
  59 #include "gimple-iterator.h"
  60 #include "tree-ssa-loop.h"
  61 #include "tree-pass.h"
  62 #include "cfgloop.h"
  63 #include "tree-data-ref.h"
  64 #include "sese.h"
  65 #include "tree-ssa-loop-manip.h"
  66 #include "tree-scalar-evolution.h"
  67 #include "gimple-ssa.h"
  68 #include "tree-into-ssa.h"
  69 #include <map>
  70
  71 #ifdef HAVE_isl
  72 #include "graphite-poly.h"
  73 #include "graphite-isl-ast-to-gimple.h"
  74
  75 /* This flag is set when an error occurred during the translation of
  76    ISL AST to Gimple.  */
  77
  78 static bool graphite_regenerate_error;
  79
  80 /* We always try to use signed 128 bit types, but fall back to smaller types
  81    in case a platform does not provide types of these sizes. In the future we
  82    should use isl to derive the optimal type for each subexpression.  */
  83
  84 static int max_mode_int_precision =
  85   GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0));
  86 static int graphite_expression_type_precision = 128 <= max_mode_int_precision ?
  87                                                 128 : max_mode_int_precision;
  88
  89 struct ast_build_info
  90 {
  91   ast_build_info()
  92     : is_parallelizable(false)
  93   { };
  94   bool is_parallelizable;
  95 };
  96
  97 /* Converts a GMP constant VAL to a tree and returns it.  */
  98
  99 static tree
 100 gmp_cst_to_tree (tree type, mpz_t val)
 101 {
 102   tree t = type ? type : integer_type_node;
 103   mpz_t tmp;
 104
 105   mpz_init (tmp);
 106   mpz_set (tmp, val);
 107   wide_int wi = wi::from_mpz (t, tmp, true);
 108   mpz_clear (tmp);
 109
 110   return wide_int_to_tree (t, wi);
 111 }
 112
 113 /* Verifies properties that GRAPHITE should maintain during translation.  */
 114
 115 static inline void
 116 graphite_verify (void)
 117 {
 118 #ifdef ENABLE_CHECKING
 119   verify_loop_structure ();
 120   verify_loop_closed_ssa (true);
 121 #endif
 122 }
 123
 124 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
 125    to corresponding trees.  */
 126
 127 typedef std::map<isl_id *, tree> ivs_params;
 128
 129 /* Free all memory allocated for ISL's identifiers.  */
 130
 131 void ivs_params_clear (ivs_params &ip)
 132 {
 133   std::map<isl_id *, tree>::iterator it;
 134   for (it = ip.begin ();
 135        it != ip.end (); it++)
 136     {
 137       isl_id_free (it->first);
 138     }
 139 }
 140
 141 static tree
 142 gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *,
 143                                     ivs_params &ip);
 144
 145 /* Return the tree variable that corresponds to the given isl ast identifier
 146    expression (an isl_ast_expr of type isl_ast_expr_id).
 147
 148    FIXME: We should replace blind conversation of id's type with derivation
 149    of the optimal type when we get the corresponding isl support. Blindly
 150    converting type sizes may be problematic when we switch to smaller
 151    types.  */
 152
 153 static tree
 154 gcc_expression_from_isl_ast_expr_id (tree type,
 155                                      __isl_keep isl_ast_expr *expr_id,
 156                                      ivs_params &ip)
 157 {
 158   gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
 159   isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
 160   std::map<isl_id *, tree>::iterator res;
 161   res = ip.find (tmp_isl_id);
 162   isl_id_free (tmp_isl_id);
 163   gcc_assert (res != ip.end () &&
 164               "Could not map isl_id to tree expression");
 165   isl_ast_expr_free (expr_id);
 166   return fold_convert (type, res->second);
 167 }
 168
 169 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
 170    type TYPE.  */
 171
 172 static tree
 173 gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr)
 174 {
 175   gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
 176   isl_val *val = isl_ast_expr_get_val (expr);
 177   mpz_t val_mpz_t;
 178   mpz_init (val_mpz_t);
 179   tree res;
 180   if (isl_val_get_num_gmp (val, val_mpz_t) == -1)
 181     res = NULL_TREE;
 182   else
 183     res = gmp_cst_to_tree (type, val_mpz_t);
 184   isl_val_free (val);
 185   isl_ast_expr_free (expr);
 186   mpz_clear (val_mpz_t);
 187   return res;
 188 }
 189
 190 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
 191    type TYPE.  */
 192
 193 static tree
 194 binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
 195 {
 196   isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
 197   tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
 198   arg_expr = isl_ast_expr_get_op_arg (expr, 1);
 199   tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
 200   enum isl_ast_op_type expr_type = isl_ast_expr_get_op_type (expr);
 201   isl_ast_expr_free (expr);
 202   switch (expr_type)
 203     {
 204     case isl_ast_op_add:
 205       return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 206
 207     case isl_ast_op_sub:
 208       return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 209
 210     case isl_ast_op_mul:
 211       return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 212
 213     case isl_ast_op_div:
 214       return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 215
 216     case isl_ast_op_pdiv_q:
 217       return fold_build2 (TRUNC_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 218
 219     case isl_ast_op_pdiv_r:
 220       return fold_build2 (TRUNC_MOD_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 221
 222     case isl_ast_op_fdiv_q:
 223       return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 224
 225     case isl_ast_op_and:
 226       return fold_build2 (TRUTH_ANDIF_EXPR, type,
 227                           tree_lhs_expr, tree_rhs_expr);
 228
 229     case isl_ast_op_or:
 230       return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 231
 232     case isl_ast_op_eq:
 233       return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 234
 235     case isl_ast_op_le:
 236       return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 237
 238     case isl_ast_op_lt:
 239       return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 240
 241     case isl_ast_op_ge:
 242       return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 243
 244     case isl_ast_op_gt:
 245       return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 246
 247     default:
 248       gcc_unreachable ();
 249     }
 250 }
 251
 252 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
 253    type TYPE.  */
 254
 255 static tree
 256 ternary_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_first_expr
 261     = gcc_expression_from_isl_expression (type, arg_expr, ip);
 262   arg_expr = isl_ast_expr_get_op_arg (expr, 1);
 263   tree tree_second_expr
 264     = gcc_expression_from_isl_expression (type, arg_expr, ip);
 265   arg_expr = isl_ast_expr_get_op_arg (expr, 2);
 266   tree tree_third_expr
 267     = gcc_expression_from_isl_expression (type, arg_expr, ip);
 268   isl_ast_expr_free (expr);
 269   return fold_build3 (COND_EXPR, type, tree_first_expr,
 270                       tree_second_expr, tree_third_expr);
 271 }
 272
 273 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
 274    type TYPE.  */
 275
 276 static tree
 277 unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
 278 {
 279   gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
 280   isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
 281   tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
 282   isl_ast_expr_free (expr);
 283   return fold_build1 (NEGATE_EXPR, type, tree_expr);
 284 }
 285
 286 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
 287    to a GCC expression tree of type TYPE.  */
 288
 289 static tree
 290 nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
 291 {
 292   enum tree_code op_code;
 293   switch (isl_ast_expr_get_op_type (expr))
 294     {
 295     case isl_ast_op_max:
 296       op_code = MAX_EXPR;
 297       break;
 298
 299     case isl_ast_op_min:
 300       op_code = MIN_EXPR;
 301       break;
 302
 303     default:
 304       gcc_unreachable ();
 305     }
 306   isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
 307   tree res = gcc_expression_from_isl_expression (type, arg_expr, ip);
 308   int i;
 309   for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
 310     {
 311       arg_expr = isl_ast_expr_get_op_arg (expr, i);
 312       tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
 313       res = fold_build2 (op_code, type, res, t);
 314     }
 315   isl_ast_expr_free (expr);
 316   return res;
 317 }
 318
 319
 320 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
 321    type TYPE.  */
 322
 323 static tree
 324 gcc_expression_from_isl_expr_op (tree type, __isl_take isl_ast_expr *expr,
 325                                  ivs_params &ip)
 326 {
 327   gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
 328   switch (isl_ast_expr_get_op_type (expr))
 329     {
 330     /* These isl ast expressions are not supported yet.  */
 331     case isl_ast_op_error:
 332     case isl_ast_op_call:
 333     case isl_ast_op_and_then:
 334     case isl_ast_op_or_else:
 335     case isl_ast_op_select:
 336       gcc_unreachable ();
 337
 338     case isl_ast_op_max:
 339     case isl_ast_op_min:
 340       return nary_op_to_tree (type, expr, ip);
 341
 342     case isl_ast_op_add:
 343     case isl_ast_op_sub:
 344     case isl_ast_op_mul:
 345     case isl_ast_op_div:
 346     case isl_ast_op_pdiv_q:
 347     case isl_ast_op_pdiv_r:
 348     case isl_ast_op_fdiv_q:
 349     case isl_ast_op_and:
 350     case isl_ast_op_or:
 351     case isl_ast_op_eq:
 352     case isl_ast_op_le:
 353     case isl_ast_op_lt:
 354     case isl_ast_op_ge:
 355     case isl_ast_op_gt:
 356       return binary_op_to_tree (type, expr, ip);
 357
 358     case isl_ast_op_minus:
 359       return unary_op_to_tree (type, expr, ip);
 360
 361     case isl_ast_op_cond:
 362       return ternary_op_to_tree (type, expr, ip);
 363
 364     default:
 365       gcc_unreachable ();
 366     }
 367
 368   return NULL_TREE;
 369 }
 370
 371 /* Converts an ISL AST expression E back to a GCC expression tree of
 372    type TYPE.  */
 373
 374 static tree
 375 gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *expr,
 376                                     ivs_params &ip)
 377 {
 378   switch (isl_ast_expr_get_type (expr))
 379     {
 380     case isl_ast_expr_id:
 381       return gcc_expression_from_isl_ast_expr_id (type, expr, ip);
 382
 383     case isl_ast_expr_int:
 384       return gcc_expression_from_isl_expr_int (type, expr);
 385
 386     case isl_ast_expr_op:
 387       return gcc_expression_from_isl_expr_op (type, expr, ip);
 388
 389     default:
 390       gcc_unreachable ();
 391     }
 392
 393   return NULL_TREE;
 394 }
 395
 396 /* Creates a new LOOP corresponding to isl_ast_node_for.  Inserts an
 397    induction variable for the new LOOP.  New LOOP is attached to CFG
 398    starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
 399    becomes the child loop of the OUTER_LOOP.  NEWIVS_INDEX binds
 400    ISL's scattering name to the induction variable created for the
 401    loop of STMT.  The new induction variable is inserted in the NEWIVS
 402    vector and is of type TYPE.  */
 403
 404 static struct loop *
 405 graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for,
 406                           loop_p outer, tree type, tree lb, tree ub,
 407                           ivs_params &ip)
 408 {
 409   isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
 410   tree stride = gcc_expression_from_isl_expression (type, for_inc, ip);
 411   tree ivvar = create_tmp_var (type, "graphite_IV");
 412   tree iv, iv_after_increment;
 413   loop_p loop = create_empty_loop_on_edge
 414     (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
 415      outer ? outer : entry_edge->src->loop_father);
 416
 417   isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
 418   isl_id *id = isl_ast_expr_get_id (for_iterator);
 419   std::map<isl_id *, tree>::iterator res;
 420   res = ip.find (id);
 421   if (ip.count (id))
 422     isl_id_free (res->first);
 423   ip[id] = iv;
 424   isl_ast_expr_free (for_iterator);
 425   return loop;
 426 }
 427
 428 static edge
 429 translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
 430                    edge next_e, ivs_params &ip);
 431
 432 /* Create the loop for a isl_ast_node_for.
 433
 434    - NEXT_E is the edge where new generated code should be attached.  */
 435
 436 static edge
 437 translate_isl_ast_for_loop (loop_p context_loop,
 438                             __isl_keep isl_ast_node *node_for, edge next_e,
 439                             tree type, tree lb, tree ub,
 440                             ivs_params &ip)
 441 {
 442   gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
 443   struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
 444                                                 type, lb, ub, ip);
 445   edge last_e = single_exit (loop);
 446   edge to_body = single_succ_edge (loop->header);
 447   basic_block after = to_body->dest;
 448
 449   /* Create a basic block for loop close phi nodes.  */
 450   last_e = single_succ_edge (split_edge (last_e));
 451
 452   /* Translate the body of the loop.  */
 453   isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
 454   next_e = translate_isl_ast (loop, for_body, to_body, ip);
 455   isl_ast_node_free (for_body);
 456   redirect_edge_succ_nodup (next_e, after);
 457   set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
 458
 459   if (flag_loop_parallelize_all)
 460   {
 461     isl_id *id = isl_ast_node_get_annotation (node_for);
 462     gcc_assert (id);
 463     ast_build_info *for_info = (ast_build_info *) isl_id_get_user (id);
 464     loop->can_be_parallel = for_info->is_parallelizable;
 465     free (for_info);
 466     isl_id_free (id);
 467   }
 468
 469   return last_e;
 470 }
 471
 472 /* We use this function to get the upper bound because of the form,
 473    which is used by isl to represent loops:
 474
 475    for (iterator = init; cond; iterator += inc)
 476
 477    {
 478
 479      ...
 480
 481    }
 482
 483    The loop condition is an arbitrary expression, which contains the
 484    current loop iterator.
 485
 486    (e.g. iterator + 3 < B && C > iterator + A)
 487
 488    We have to know the upper bound of the iterator to generate a loop
 489    in Gimple form. It can be obtained from the special representation
 490    of the loop condition, which is generated by isl,
 491    if the ast_build_atomic_upper_bound option is set. In this case,
 492    isl generates a loop condition that consists of the current loop
 493    iterator, + an operator (< or <=) and an expression not involving
 494    the iterator, which is processed and returned by this function.
 495
 496    (e.g iterator <= upper-bound-expression-without-iterator)  */
 497
 498 static __isl_give isl_ast_expr *
 499 get_upper_bound (__isl_keep isl_ast_node *node_for)
 500 {
 501   gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
 502   isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
 503   gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
 504   isl_ast_expr *res;
 505   switch (isl_ast_expr_get_op_type (for_cond))
 506     {
 507     case isl_ast_op_le:
 508       res = isl_ast_expr_get_op_arg (for_cond, 1);
 509       break;
 510
 511     case isl_ast_op_lt:
 512       {
 513         // (iterator < ub) => (iterator <= ub - 1)
 514         isl_val *one =
 515           isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
 516         isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
 517         res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
 518         break;
 519       }
 520
 521     default:
 522       gcc_unreachable ();
 523     }
 524   isl_ast_expr_free (for_cond);
 525   return res;
 526 }
 527
 528 /* All loops generated by create_empty_loop_on_edge have the form of
 529    a post-test loop:
 530
 531    do
 532
 533    {
 534      body of the loop;
 535    } while (lower bound < upper bound);
 536
 537    We create a new if region protecting the loop to be executed, if
 538    the execution count is zero (lower bound > upper bound).  */
 539
 540 static edge
 541 graphite_create_new_loop_guard (edge entry_edge,
 542                                 __isl_keep isl_ast_node *node_for, tree *type,
 543                                 tree *lb, tree *ub, ivs_params &ip)
 544 {
 545   gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
 546   tree cond_expr;
 547   edge exit_edge;
 548
 549   *type =
 550     build_nonstandard_integer_type (graphite_expression_type_precision, 0);
 551   isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
 552   *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
 553   isl_ast_expr *upper_bound = get_upper_bound (node_for);
 554   *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip);
 555
 556   /* When ub is simply a constant or a parameter, use lb <= ub.  */
 557   if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
 558     cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
 559   else
 560     {
 561       tree one = (POINTER_TYPE_P (*type)
 562                   ? convert_to_ptrofftype (integer_one_node)
 563                   : fold_convert (*type, integer_one_node));
 564       /* Adding +1 and using LT_EXPR helps with loop latches that have a
 565          loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this
 566          becomes 2^k-1 due to integer overflow, and the condition lb <= ub
 567          is true, even if we do not want this.  However lb < ub + 1 is false,
 568          as expected.  */
 569       tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
 570                                  : PLUS_EXPR, *type, *ub, one);
 571
 572       cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
 573     }
 574
 575   exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
 576
 577   return exit_edge;
 578 }
 579
 580 /* Translates an isl_ast_node_for to Gimple. */
 581
 582 static edge
 583 translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node,
 584                             edge next_e, ivs_params &ip)
 585 {
 586   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for);
 587   tree type, lb, ub;
 588   edge last_e = graphite_create_new_loop_guard (next_e, node, &type,
 589                                                 &lb, &ub, ip);
 590   edge true_e = get_true_edge_from_guard_bb (next_e->dest);
 591
 592   translate_isl_ast_for_loop (context_loop, node, true_e,
 593                               type, lb, ub, ip);
 594   return last_e;
 595 }
 596
 597 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
 598    variables of the loops around GBB in SESE.
 599
 600    FIXME: Instead of using a vec<tree> that maps each loop id to a possible
 601    chrec, we could consider using a map<int, tree> that maps loop ids to the
 602    corresponding tree expressions.  */
 603
 604 static void
 605 build_iv_mapping (vec<tree> iv_map, gimple_bb_p gbb,
 606                   __isl_keep isl_ast_expr *user_expr, ivs_params &ip,
 607                   sese region)
 608 {
 609   gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op &&
 610               isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call);
 611   int i;
 612   isl_ast_expr *arg_expr;
 613   for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++)
 614     {
 615       arg_expr = isl_ast_expr_get_op_arg (user_expr, i);
 616       tree type =
 617         build_nonstandard_integer_type (graphite_expression_type_precision, 0);
 618       tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
 619       loop_p old_loop = gbb_loop_at_index (gbb, region, i - 1);
 620       iv_map[old_loop->num] = t;
 621     }
 622
 623 }
 624
 625 /* Translates an isl_ast_node_user to Gimple.
 626
 627    FIXME: We should remove iv_map.create (loop->num + 1), if it is possible.  */
 628
 629 static edge
 630 translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
 631                              edge next_e, ivs_params &ip)
 632 {
 633   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user);
 634   isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node);
 635   isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0);
 636   gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id);
 637   isl_id *name_id = isl_ast_expr_get_id (name_expr);
 638   poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id);
 639   gcc_assert (pbb);
 640   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
 641   vec<tree> iv_map;
 642   isl_ast_expr_free (name_expr);
 643   isl_id_free (name_id);
 644
 645   gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
 646               "The entry block should not even appear within a scop");
 647
 648   int nb_loops = number_of_loops (cfun);
 649   iv_map.create (nb_loops);
 650   iv_map.safe_grow_cleared (nb_loops);
 651
 652   build_iv_mapping (iv_map, gbb, user_expr, ip, SCOP_REGION (pbb->scop));
 653   isl_ast_expr_free (user_expr);
 654   next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb),
 655                                            SCOP_REGION (pbb->scop), next_e,
 656                                            iv_map,
 657                                            &graphite_regenerate_error);
 658   iv_map.release ();
 659   mark_virtual_operands_for_renaming (cfun);
 660   update_ssa (TODO_update_ssa);
 661   return next_e;
 662 }
 663
 664 /* Translates an isl_ast_node_block to Gimple. */
 665
 666 static edge
 667 translate_isl_ast_node_block (loop_p context_loop,
 668                               __isl_keep isl_ast_node *node,
 669                               edge next_e, ivs_params &ip)
 670 {
 671   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_block);
 672   isl_ast_node_list *node_list = isl_ast_node_block_get_children (node);
 673   int i;
 674   for (i = 0; i < isl_ast_node_list_n_ast_node (node_list); i++)
 675     {
 676       isl_ast_node *tmp_node = isl_ast_node_list_get_ast_node (node_list, i);
 677       next_e = translate_isl_ast (context_loop, tmp_node, next_e, ip);
 678       isl_ast_node_free (tmp_node);
 679     }
 680   isl_ast_node_list_free (node_list);
 681   return next_e;
 682 }
 683
 684 /* Creates a new if region corresponding to ISL's cond.  */
 685
 686 static edge
 687 graphite_create_new_guard (edge entry_edge, __isl_take isl_ast_expr *if_cond,
 688                            ivs_params &ip)
 689 {
 690   tree type =
 691     build_nonstandard_integer_type (graphite_expression_type_precision, 0);
 692   tree cond_expr = gcc_expression_from_isl_expression (type, if_cond, ip);
 693   edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
 694   return exit_edge;
 695 }
 696
 697 /* Translates an isl_ast_node_if to Gimple.  */
 698
 699 static edge
 700 translate_isl_ast_node_if (loop_p context_loop,
 701                            __isl_keep isl_ast_node *node,
 702                            edge next_e, ivs_params &ip)
 703 {
 704   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_if);
 705   isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node);
 706   edge last_e = graphite_create_new_guard (next_e, if_cond, ip);
 707
 708   edge true_e = get_true_edge_from_guard_bb (next_e->dest);
 709   isl_ast_node *then_node = isl_ast_node_if_get_then (node);
 710   translate_isl_ast (context_loop, then_node, true_e, ip);
 711   isl_ast_node_free (then_node);
 712
 713   edge false_e = get_false_edge_from_guard_bb (next_e->dest);
 714   isl_ast_node *else_node = isl_ast_node_if_get_else (node);
 715   if (isl_ast_node_get_type (else_node) != isl_ast_node_error)
 716     translate_isl_ast (context_loop, else_node, false_e, ip);
 717   isl_ast_node_free (else_node);
 718   return last_e;
 719 }
 720
 721 /* Translates an ISL AST node NODE to GCC representation in the
 722    context of a SESE.  */
 723
 724 static edge
 725 translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
 726                    edge next_e, ivs_params &ip)
 727 {
 728   switch (isl_ast_node_get_type (node))
 729     {
 730     case isl_ast_node_error:
 731       gcc_unreachable ();
 732
 733     case isl_ast_node_for:
 734       return translate_isl_ast_node_for (context_loop, node,
 735                                          next_e, ip);
 736
 737     case isl_ast_node_if:
 738       return translate_isl_ast_node_if (context_loop, node,
 739                                         next_e, ip);
 740
 741     case isl_ast_node_user:
 742       return translate_isl_ast_node_user (node, next_e, ip);
 743
 744     case isl_ast_node_block:
 745       return translate_isl_ast_node_block (context_loop, node,
 746                                            next_e, ip);
 747
 748     default:
 749       gcc_unreachable ();
 750     }
 751 }
 752
 753 /* Prints NODE to FILE.  */
 754
 755 void
 756 print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node,
 757                     __isl_keep isl_ctx *ctx)
 758 {
 759   isl_printer *prn = isl_printer_to_file (ctx, file);
 760   prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
 761   prn = isl_printer_print_ast_node (prn, node);
 762   prn = isl_printer_print_str (prn, "\n");
 763   isl_printer_free (prn);
 764 }
 765
 766 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params  */
 767
 768 static void
 769 add_parameters_to_ivs_params (scop_p scop, ivs_params &ip)
 770 {
 771   sese region = SCOP_REGION (scop);
 772   unsigned nb_parameters = isl_set_dim (scop->context, isl_dim_param);
 773   gcc_assert (nb_parameters == SESE_PARAMS (region).length ());
 774   unsigned i;
 775   for (i = 0; i < nb_parameters; i++)
 776     {
 777       isl_id *tmp_id = isl_set_get_dim_id (scop->context, isl_dim_param, i);
 778       ip[tmp_id] = SESE_PARAMS (region)[i];
 779     }
 780 }
 781
 782
 783 /* Generates a build, which specifies the constraints on the parameters.  */
 784
 785 static __isl_give isl_ast_build *
 786 generate_isl_context (scop_p scop)
 787 {
 788   isl_set *context_isl = isl_set_params (isl_set_copy (scop->context));
 789   return isl_ast_build_from_context (context_isl);
 790 }
 791
 792 /* Get the maximal number of schedule dimensions in the scop SCOP.  */
 793
 794 static
 795 int get_max_schedule_dimensions (scop_p scop)
 796 {
 797   int i;
 798   poly_bb_p pbb;
 799   int schedule_dims = 0;
 800
 801   FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
 802     {
 803       int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out);
 804       if (pbb_schedule_dims > schedule_dims)
 805         schedule_dims = pbb_schedule_dims;
 806     }
 807
 808   return schedule_dims;
 809 }
 810
 811 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
 812
 813    For schedules with different dimensionality, the isl AST generator can not
 814    define an order and will just randomly choose an order. The solution to this
 815    problem is to extend all schedules to the maximal number of schedule
 816    dimensions (using '0's for the remaining values).  */
 817
 818 static __isl_give isl_map *
 819 extend_schedule (__isl_take isl_map *schedule, int nb_schedule_dims)
 820 {
 821   int tmp_dims = isl_map_dim (schedule, isl_dim_out);
 822   schedule =
 823     isl_map_add_dims (schedule, isl_dim_out, nb_schedule_dims - tmp_dims);
 824   isl_val *zero =
 825     isl_val_int_from_si (isl_map_get_ctx (schedule), 0);
 826   int i;
 827   for (i = tmp_dims; i < nb_schedule_dims; i++)
 828     {
 829       schedule =
 830         isl_map_fix_val (schedule, isl_dim_out, i, isl_val_copy (zero));
 831     }
 832   isl_val_free (zero);
 833   return schedule;
 834 }
 835
 836 /* Set the separation_class option for unroll and jam. */
 837
 838 static __isl_give isl_union_map *
 839 generate_luj_sepclass_opt (scop_p scop, __isl_take isl_union_set *domain,
 840                         int dim, int cl)
 841 {
 842   isl_map  *map;
 843   isl_space *space, *space_sep;
 844   isl_ctx *ctx;
 845   isl_union_map *mapu;
 846   int nsched = get_max_schedule_dimensions (scop);
 847
 848   ctx = scop->ctx;
 849   space_sep = isl_space_alloc (ctx, 0, 1, 1);
 850   space_sep = isl_space_wrap (space_sep);
 851   space_sep = isl_space_set_tuple_name (space_sep, isl_dim_set,
 852                                         "separation_class");
 853   space = isl_set_get_space (scop->context);
 854   space_sep = isl_space_align_params (space_sep, isl_space_copy(space));
 855   space = isl_space_map_from_domain_and_range (space, space_sep);
 856   space = isl_space_add_dims (space,isl_dim_in, nsched);
 857   map = isl_map_universe (space);
 858   isl_map_fix_si (map,isl_dim_out,0,dim);
 859   isl_map_fix_si (map,isl_dim_out,1,cl);
 860
 861   mapu = isl_union_map_intersect_domain (isl_union_map_from_map (map),
 862                                          domain);
 863   return (mapu);
 864 }
 865
 866 /* Compute the separation class for loop unroll and jam.  */
 867
 868 static __isl_give isl_union_set *
 869 generate_luj_sepclass (scop_p scop)
 870 {
 871   int i;
 872   poly_bb_p pbb;
 873   isl_union_set *domain_isl;
 874
 875   domain_isl = isl_union_set_empty (isl_set_get_space (scop->context));
 876
 877   FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
 878     {
 879       isl_set *bb_domain;
 880       isl_set *bb_domain_s;
 881
 882       if (pbb->map_sepclass == NULL)
 883         continue;
 884
 885       if (isl_set_is_empty (pbb->domain))
 886         continue;
 887
 888       bb_domain = isl_set_copy (pbb->domain);
 889       bb_domain_s = isl_set_apply (bb_domain, pbb->map_sepclass);
 890       pbb->map_sepclass = NULL;
 891
 892       domain_isl =
 893         isl_union_set_union (domain_isl, isl_union_set_from_set (bb_domain_s));
 894     }
 895
 896   return domain_isl;
 897 }
 898
 899 /* Set the AST built options for loop unroll and jam. */
 900
 901 static __isl_give isl_union_map *
 902 generate_luj_options (scop_p scop)
 903 {
 904   isl_union_set *domain_isl;
 905   isl_union_map *options_isl_ss;
 906   isl_union_map *options_isl =
 907     isl_union_map_empty (isl_set_get_space (scop->context));
 908   int dim = get_max_schedule_dimensions (scop) - 1;
 909   int dim1 = dim - PARAM_VALUE (PARAM_LOOP_UNROLL_JAM_DEPTH);
 910
 911   if (!flag_loop_unroll_jam)
 912     return options_isl;
 913
 914   domain_isl = generate_luj_sepclass (scop);
 915
 916   options_isl_ss = generate_luj_sepclass_opt (scop, domain_isl, dim1, 0);
 917   options_isl = isl_union_map_union (options_isl, options_isl_ss);
 918
 919   return options_isl;
 920 }
 921
 922 /* Generates a schedule, which specifies an order used to
 923    visit elements in a domain.  */
 924
 925 static __isl_give isl_union_map *
 926 generate_isl_schedule (scop_p scop)
 927 {
 928   int nb_schedule_dims = get_max_schedule_dimensions (scop);
 929   int i;
 930   poly_bb_p pbb;
 931   isl_union_map *schedule_isl =
 932     isl_union_map_empty (isl_set_get_space (scop->context));
 933
 934   FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
 935     {
 936       /* Dead code elimination: when the domain of a PBB is empty,
 937          don't generate code for the PBB.  */
 938       if (isl_set_is_empty (pbb->domain))
 939         continue;
 940
 941       isl_map *bb_schedule = isl_map_copy (pbb->transformed);
 942       bb_schedule = isl_map_intersect_domain (bb_schedule,
 943                                               isl_set_copy (pbb->domain));
 944       bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims);
 945       schedule_isl =
 946         isl_union_map_union (schedule_isl,
 947                              isl_union_map_from_map (bb_schedule));
 948     }
 949   return schedule_isl;
 950 }
 951
 952 /* This method is executed before the construction of a for node.  */
 953 static __isl_give isl_id *
 954 ast_build_before_for (__isl_keep isl_ast_build *build, void *user)
 955 {
 956   isl_union_map *dependences = (isl_union_map *) user;
 957   ast_build_info *for_info = XNEW (struct ast_build_info);
 958   isl_union_map *schedule = isl_ast_build_get_schedule (build);
 959   isl_space *schedule_space = isl_ast_build_get_schedule_space (build);
 960   int dimension = isl_space_dim (schedule_space, isl_dim_out);
 961   for_info->is_parallelizable =
 962     !carries_deps (schedule, dependences, dimension);
 963   isl_union_map_free (schedule);
 964   isl_space_free (schedule_space);
 965   isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info);
 966   return id;
 967 }
 968
 969 /* Set the separate option for all dimensions.
 970    This helps to reduce control overhead.
 971    Set the options for unroll and jam.  */
 972
 973 static __isl_give isl_ast_build *
 974 set_options (__isl_take isl_ast_build *control,
 975              __isl_keep isl_union_map *schedule,
 976              __isl_take isl_union_map *opt_luj)
 977 {
 978   isl_ctx *ctx = isl_union_map_get_ctx (schedule);
 979   isl_space *range_space = isl_space_set_alloc (ctx, 0, 1);
 980   range_space =
 981     isl_space_set_tuple_name (range_space, isl_dim_set, "separate");
 982   isl_union_set *range =
 983     isl_union_set_from_set (isl_set_universe (range_space));
 984   isl_union_set *domain = isl_union_map_range (isl_union_map_copy (schedule));
 985   domain = isl_union_set_universe (domain);
 986   isl_union_map *options = isl_union_map_from_domain_and_range (domain, range);
 987
 988   options = isl_union_map_union (options, opt_luj);
 989
 990   return isl_ast_build_set_options (control, options);
 991 }
 992
 993 static __isl_give isl_ast_node *
 994 scop_to_isl_ast (scop_p scop, ivs_params &ip)
 995 {
 996   /* Generate loop upper bounds that consist of the current loop iterator,
 997   an operator (< or <=) and an expression not involving the iterator.
 998   If this option is not set, then the current loop iterator may appear several
 999   times in the upper bound. See the isl manual for more details.  */
1000   isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
1001
1002   add_parameters_to_ivs_params (scop, ip);
1003
1004   isl_union_map *options_luj = generate_luj_options (scop);
1005
1006   isl_union_map *schedule_isl = generate_isl_schedule (scop);
1007   isl_ast_build *context_isl = generate_isl_context (scop);
1008
1009   context_isl = set_options (context_isl, schedule_isl, options_luj);
1010
1011   isl_union_map *dependences = NULL;
1012   if (flag_loop_parallelize_all)
1013   {
1014     dependences = scop_get_dependences (scop);
1015     context_isl =
1016       isl_ast_build_set_before_each_for (context_isl, ast_build_before_for,
1017                                          dependences);
1018   }
1019   isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
1020                                                            schedule_isl);
1021   if(dependences)
1022     isl_union_map_free (dependences);
1023   isl_ast_build_free (context_isl);
1024   return ast_isl;
1025 }
1026
1027 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1028    the given SCOP.  Return true if code generation succeeded.
1029
1030    FIXME: This is not yet a full implementation of the code generator
1031           with ISL ASTs. Generation of GIMPLE code has to be completed.  */
1032
1033 bool
1034 graphite_regenerate_ast_isl (scop_p scop)
1035 {
1036   loop_p context_loop;
1037   sese region = SCOP_REGION (scop);
1038   ifsese if_region = NULL;
1039   isl_ast_node *root_node;
1040   ivs_params ip;
1041
1042   timevar_push (TV_GRAPHITE_CODE_GEN);
1043   graphite_regenerate_error = false;
1044   root_node = scop_to_isl_ast (scop, ip);
1045
1046   if (dump_file && (dump_flags & TDF_DETAILS))
1047     {
1048       fprintf (dump_file, "\nISL AST generated by ISL: \n");
1049       print_isl_ast_node (dump_file, root_node, scop->ctx);
1050       fprintf (dump_file, "\n");
1051     }
1052
1053   recompute_all_dominators ();
1054   graphite_verify ();
1055
1056   if_region = move_sese_in_condition (region);
1057   sese_insert_phis_for_liveouts (region,
1058                                  if_region->region->exit->src,
1059                                  if_region->false_region->exit,
1060                                  if_region->true_region->exit);
1061   recompute_all_dominators ();
1062   graphite_verify ();
1063
1064   context_loop = SESE_ENTRY (region)->src->loop_father;
1065
1066   translate_isl_ast (context_loop, root_node, if_region->true_region->entry,
1067                      ip);
1068   graphite_verify ();
1069   scev_reset ();
1070   recompute_all_dominators ();
1071   graphite_verify ();
1072
1073   if (graphite_regenerate_error)
1074     set_ifsese_condition (if_region, integer_zero_node);
1075
1076   free (if_region->true_region);
1077   free (if_region->region);
1078   free (if_region);
1079
1080   ivs_params_clear (ip);
1081   isl_ast_node_free (root_node);
1082   timevar_pop (TV_GRAPHITE_CODE_GEN);
1083
1084   if (dump_file && (dump_flags & TDF_DETAILS))
1085     {
1086       loop_p loop;
1087       int num_no_dependency = 0;
1088
1089       FOR_EACH_LOOP (loop, 0)
1090         if (loop->can_be_parallel)
1091           num_no_dependency++;
1092
1093       fprintf (dump_file, "\n%d loops carried no dependency.\n",
1094                num_no_dependency);
1095     }
1096
1097   return !graphite_regenerate_error;
1098 }
1099 #endif