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