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