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