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

   1 /* Translation of ISL AST to Gimple.
   2    Copyright (C) 2014 Free Software Foundation, Inc.
   3    Contributed by Roman Gareev <gareevroman@gmail.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22
  23 #ifdef HAVE_isl
  24 #include <isl/set.h>
  25 #include <isl/map.h>
  26 #include <isl/union_map.h>
  27 #include <isl/ast_build.h>
  28 #if defined(__cplusplus)
  29 extern "C" {
  30 #endif
  31 #include <isl/val_gmp.h>
  32 #if defined(__cplusplus)
  33 }
  34 #endif
  35 #endif
  36
  37 #include "system.h"
  38 #include "coretypes.h"
  39 #include "tree.h"
  40 #include "predict.h"
  41 #include "vec.h"
  42 #include "hashtab.h"
  43 #include "hash-set.h"
  44 #include "machmode.h"
  45 #include "tm.h"
  46 #include "hard-reg-set.h"
  47 #include "input.h"
  48 #include "function.h"
  49 #include "dominance.h"
  50 #include "cfg.h"
  51 #include "basic-block.h"
  52 #include "tree-ssa-alias.h"
  53 #include "internal-fn.h"
  54 #include "gimple-expr.h"
  55 #include "is-a.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 /* Generates a schedule, which specifies an order used to
 835    visit elements in a domain.  */
 836
 837 static __isl_give isl_union_map *
 838 generate_isl_schedule (scop_p scop)
 839 {
 840   int nb_schedule_dims = get_max_schedule_dimensions (scop);
 841   int i;
 842   poly_bb_p pbb;
 843   isl_union_map *schedule_isl =
 844     isl_union_map_empty (isl_set_get_space (scop->context));
 845
 846   FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
 847     {
 848       /* Dead code elimination: when the domain of a PBB is empty,
 849          don't generate code for the PBB.  */
 850       if (isl_set_is_empty (pbb->domain))
 851         continue;
 852
 853       isl_map *bb_schedule = isl_map_copy (pbb->transformed);
 854       bb_schedule = isl_map_intersect_domain (bb_schedule,
 855                                               isl_set_copy (pbb->domain));
 856       bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims);
 857       schedule_isl =
 858         isl_union_map_union (schedule_isl,
 859                              isl_union_map_from_map (bb_schedule));
 860     }
 861   return schedule_isl;
 862 }
 863
 864 /* This method is executed before the construction of a for node.  */
 865 static __isl_give isl_id *
 866 ast_build_before_for (__isl_keep isl_ast_build *build, void *user)
 867 {
 868   isl_union_map *dependences = (isl_union_map *) user;
 869   ast_build_info *for_info = XNEW (struct ast_build_info);
 870   isl_union_map *schedule = isl_ast_build_get_schedule (build);
 871   isl_space *schedule_space = isl_ast_build_get_schedule_space (build);
 872   int dimension = isl_space_dim (schedule_space, isl_dim_out);
 873   for_info->is_parallelizable =
 874     !carries_deps (schedule, dependences, dimension);
 875   isl_union_map_free (schedule);
 876   isl_space_free (schedule_space);
 877   isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info);
 878   return id;
 879 }
 880
 881 /* Set the separate option for all dimensions.
 882    This helps to reduce control overhead.  */
 883
 884 static __isl_give isl_ast_build *
 885 set_options (__isl_take isl_ast_build *control,
 886              __isl_keep isl_union_map *schedule)
 887 {
 888   isl_ctx *ctx = isl_union_map_get_ctx (schedule);
 889   isl_space *range_space = isl_space_set_alloc (ctx, 0, 1);
 890   range_space =
 891     isl_space_set_tuple_name (range_space, isl_dim_set, "separate");
 892   isl_union_set *range =
 893     isl_union_set_from_set (isl_set_universe (range_space));
 894   isl_union_set *domain = isl_union_map_range (isl_union_map_copy (schedule));
 895   domain = isl_union_set_universe (domain);
 896   isl_union_map *options = isl_union_map_from_domain_and_range (domain, range);
 897   return isl_ast_build_set_options (control, options);
 898 }
 899
 900 static __isl_give isl_ast_node *
 901 scop_to_isl_ast (scop_p scop, ivs_params &ip)
 902 {
 903   /* Generate loop upper bounds that consist of the current loop iterator,
 904   an operator (< or <=) and an expression not involving the iterator.
 905   If this option is not set, then the current loop iterator may appear several
 906   times in the upper bound. See the isl manual for more details.  */
 907   isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
 908
 909   add_parameters_to_ivs_params (scop, ip);
 910   isl_union_map *schedule_isl = generate_isl_schedule (scop);
 911   isl_ast_build *context_isl = generate_isl_context (scop);
 912   context_isl = set_options (context_isl, schedule_isl);
 913   isl_union_map *dependences = NULL;
 914   if (flag_loop_parallelize_all)
 915   {
 916     dependences = scop_get_dependences (scop);
 917     context_isl =
 918       isl_ast_build_set_before_each_for (context_isl, ast_build_before_for,
 919                                          dependences);
 920   }
 921   isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
 922                                                            schedule_isl);
 923   if(dependences)
 924     isl_union_map_free (dependences);
 925   isl_ast_build_free (context_isl);
 926   return ast_isl;
 927 }
 928
 929 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
 930    the given SCOP.  Return true if code generation succeeded.
 931
 932    FIXME: This is not yet a full implementation of the code generator
 933           with ISL ASTs. Generation of GIMPLE code has to be completed.  */
 934
 935 bool
 936 graphite_regenerate_ast_isl (scop_p scop)
 937 {
 938   loop_p context_loop;
 939   sese region = SCOP_REGION (scop);
 940   ifsese if_region = NULL;
 941   isl_ast_node *root_node;
 942   ivs_params ip;
 943
 944   timevar_push (TV_GRAPHITE_CODE_GEN);
 945   graphite_regenerate_error = false;
 946   root_node = scop_to_isl_ast (scop, ip);
 947
 948   if (dump_file && (dump_flags & TDF_DETAILS))
 949     {
 950       fprintf (dump_file, "\nISL AST generated by ISL: \n");
 951       print_isl_ast_node (dump_file, root_node, scop->ctx);
 952       fprintf (dump_file, "\n");
 953     }
 954
 955   recompute_all_dominators ();
 956   graphite_verify ();
 957
 958   if_region = move_sese_in_condition (region);
 959   sese_insert_phis_for_liveouts (region,
 960                                  if_region->region->exit->src,
 961                                  if_region->false_region->exit,
 962                                  if_region->true_region->exit);
 963   recompute_all_dominators ();
 964   graphite_verify ();
 965
 966   context_loop = SESE_ENTRY (region)->src->loop_father;
 967
 968   translate_isl_ast (context_loop, root_node, if_region->true_region->entry,
 969                      ip);
 970   graphite_verify ();
 971   scev_reset ();
 972   recompute_all_dominators ();
 973   graphite_verify ();
 974
 975   if (graphite_regenerate_error)
 976     set_ifsese_condition (if_region, integer_zero_node);
 977
 978   free (if_region->true_region);
 979   free (if_region->region);
 980   free (if_region);
 981
 982   ivs_params_clear (ip);
 983   isl_ast_node_free (root_node);
 984   timevar_pop (TV_GRAPHITE_CODE_GEN);
 985
 986   if (dump_file && (dump_flags & TDF_DETAILS))
 987     {
 988       loop_p loop;
 989       int num_no_dependency = 0;
 990
 991       FOR_EACH_LOOP (loop, 0)
 992         if (loop->can_be_parallel)
 993           num_no_dependency++;
 994
 995       fprintf (dump_file, "\n%d loops carried no dependency.\n",
 996                num_no_dependency);
 997     }
 998
 999   return !graphite_regenerate_error;
1000 }
1001 #endif