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

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