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