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