gcc/graphite-isl-ast-to-gimple.c

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