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

   1 /* Translation of isl AST to Gimple.
   2    Copyright (C) 2014-2017 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 #define USES_ISL
  22
  23 #include "config.h"
  24
  25 #ifdef HAVE_isl
  26
  27 #define INCLUDE_MAP
  28 #include "system.h"
  29 #include "coretypes.h"
  30 #include "backend.h"
  31 #include "cfghooks.h"
  32 #include "tree.h"
  33 #include "gimple.h"
  34 #include "ssa.h"
  35 #include "params.h"
  36 #include "fold-const.h"
  37 #include "gimple-fold.h"
  38 #include "gimple-iterator.h"
  39 #include "gimplify.h"
  40 #include "gimplify-me.h"
  41 #include "tree-eh.h"
  42 #include "tree-ssa-loop.h"
  43 #include "tree-ssa-operands.h"
  44 #include "tree-ssa-propagate.h"
  45 #include "tree-pass.h"
  46 #include "cfgloop.h"
  47 #include "tree-data-ref.h"
  48 #include "tree-ssa-loop-manip.h"
  49 #include "tree-scalar-evolution.h"
  50 #include "gimple-ssa.h"
  51 #include "tree-phinodes.h"
  52 #include "tree-into-ssa.h"
  53 #include "ssa-iterators.h"
  54 #include "tree-cfg.h"
  55 #include "gimple-pretty-print.h"
  56 #include "cfganal.h"
  57 #include "value-prof.h"
  58 #include "tree-ssa.h"
  59 #include "graphite.h"
  60
  61 struct ast_build_info
  62 {
  63   ast_build_info()
  64     : is_parallelizable(false)
  65   { }
  66   bool is_parallelizable;
  67 };
  68
  69 /* IVS_PARAMS maps isl's scattering and parameter identifiers
  70    to corresponding trees.  */
  71
  72 typedef std::map<isl_id *, tree> ivs_params;
  73
  74 /* Free all memory allocated for isl's identifiers.  */
  75
  76 static void ivs_params_clear (ivs_params &ip)
  77 {
  78   std::map<isl_id *, tree>::iterator it;
  79   for (it = ip.begin ();
  80        it != ip.end (); it++)
  81     {
  82       isl_id_free (it->first);
  83     }
  84 }
  85
  86 /* Set the "separate" option for the schedule node.  */
  87
  88 static isl_schedule_node *
  89 set_separate_option (__isl_take isl_schedule_node *node, void *user)
  90 {
  91   if (user)
  92     return node;
  93
  94   if (isl_schedule_node_get_type (node) != isl_schedule_node_band)
  95     return node;
  96
  97   /* Set the "separate" option unless it is set earlier to another option.  */
  98   if (isl_schedule_node_band_member_get_ast_loop_type (node, 0)
  99       == isl_ast_loop_default)
 100     return isl_schedule_node_band_member_set_ast_loop_type
 101       (node, 0, isl_ast_loop_separate);
 102
 103   return node;
 104 }
 105
 106 /* Print SCHEDULE under an AST form on file F.  */
 107
 108 void
 109 print_schedule_ast (FILE *f, __isl_keep isl_schedule *schedule, scop_p scop)
 110 {
 111   isl_set *set = isl_set_params (isl_set_copy (scop->param_context));
 112   isl_ast_build *context = isl_ast_build_from_context (set);
 113   isl_ast_node *ast
 114     = isl_ast_build_node_from_schedule (context, isl_schedule_copy (schedule));
 115   isl_ast_build_free (context);
 116   print_isl_ast (f, ast);
 117   isl_ast_node_free (ast);
 118 }
 119
 120 DEBUG_FUNCTION void
 121 debug_schedule_ast (__isl_keep isl_schedule *s, scop_p scop)
 122 {
 123   print_schedule_ast (stderr, s, scop);
 124 }
 125
 126 enum phi_node_kind
 127 {
 128   unknown_phi,
 129   loop_phi,
 130   close_phi,
 131   cond_phi
 132 };
 133
 134 class translate_isl_ast_to_gimple
 135 {
 136  public:
 137   translate_isl_ast_to_gimple (sese_info_p r);
 138   edge translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
 139                           edge next_e, ivs_params &ip);
 140   edge translate_isl_ast_node_for (loop_p context_loop,
 141                                    __isl_keep isl_ast_node *node,
 142                                    edge next_e, ivs_params &ip);
 143   edge translate_isl_ast_for_loop (loop_p context_loop,
 144                                    __isl_keep isl_ast_node *node_for,
 145                                    edge next_e,
 146                                    tree type, tree lb, tree ub,
 147                                    ivs_params &ip);
 148   edge translate_isl_ast_node_if (loop_p context_loop,
 149                                   __isl_keep isl_ast_node *node,
 150                                   edge next_e, ivs_params &ip);
 151   edge translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
 152                                     edge next_e, ivs_params &ip);
 153   edge translate_isl_ast_node_block (loop_p context_loop,
 154                                      __isl_keep isl_ast_node *node,
 155                                      edge next_e, ivs_params &ip);
 156   tree unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
 157                          ivs_params &ip);
 158   tree binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
 159                           ivs_params &ip);
 160   tree ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
 161                            ivs_params &ip);
 162   tree nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
 163                         ivs_params &ip);
 164   tree gcc_expression_from_isl_expression (tree type,
 165                                            __isl_take isl_ast_expr *,
 166                                            ivs_params &ip);
 167   tree gcc_expression_from_isl_ast_expr_id (tree type,
 168                                             __isl_keep isl_ast_expr *expr_id,
 169                                             ivs_params &ip);
 170   widest_int widest_int_from_isl_expr_int (__isl_keep isl_ast_expr *expr);
 171   tree gcc_expression_from_isl_expr_int (tree type,
 172                                          __isl_take isl_ast_expr *expr);
 173   tree gcc_expression_from_isl_expr_op (tree type,
 174                                         __isl_take isl_ast_expr *expr,
 175                                         ivs_params &ip);
 176   struct loop *graphite_create_new_loop (edge entry_edge,
 177                                          __isl_keep isl_ast_node *node_for,
 178                                          loop_p outer, tree type,
 179                                          tree lb, tree ub, ivs_params &ip);
 180   edge graphite_create_new_guard (edge entry_edge,
 181                                   __isl_take isl_ast_expr *if_cond,
 182                                   ivs_params &ip);
 183   void build_iv_mapping (vec<tree> iv_map, gimple_poly_bb_p gbb,
 184                          __isl_keep isl_ast_expr *user_expr, ivs_params &ip,
 185                          sese_l &region);
 186   void add_parameters_to_ivs_params (scop_p scop, ivs_params &ip);
 187   __isl_give isl_ast_build *generate_isl_context (scop_p scop);
 188
 189   __isl_give isl_ast_node * scop_to_isl_ast (scop_p scop);
 190
 191   tree get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop,
 192                              vec<tree> iv_map);
 193   bool graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
 194                                        vec<tree> iv_map);
 195   edge copy_bb_and_scalar_dependences (basic_block bb, edge next_e,
 196                                        vec<tree> iv_map);
 197   void set_rename (tree old_name, tree expr);
 198   void gsi_insert_earliest (gimple_seq seq);
 199   bool codegen_error_p () const { return codegen_error; }
 200
 201   void set_codegen_error ()
 202   {
 203     codegen_error = true;
 204     gcc_assert (! flag_checking
 205                 || PARAM_VALUE (PARAM_GRAPHITE_ALLOW_CODEGEN_ERRORS));
 206   }
 207
 208   bool is_constant (tree op) const
 209   {
 210     return TREE_CODE (op) == INTEGER_CST
 211       || TREE_CODE (op) == REAL_CST
 212       || TREE_CODE (op) == COMPLEX_CST
 213       || TREE_CODE (op) == VECTOR_CST;
 214   }
 215
 216 private:
 217   /* The region to be translated.  */
 218   sese_info_p region;
 219
 220   /* This flag is set when an error occurred during the translation of isl AST
 221      to Gimple.  */
 222   bool codegen_error;
 223
 224   /* A vector of all the edges at if_condition merge points.  */
 225   auto_vec<edge, 2> merge_points;
 226
 227   tree graphite_expr_type;
 228 };
 229
 230 translate_isl_ast_to_gimple::translate_isl_ast_to_gimple (sese_info_p r)
 231   : region (r), codegen_error (false)
 232 {
 233   /* We always try to use signed 128 bit types, but fall back to smaller types
 234      in case a platform does not provide types of these sizes. In the future we
 235      should use isl to derive the optimal type for each subexpression.  */
 236   int max_mode_int_precision
 237     = GET_MODE_PRECISION (int_mode_for_size (MAX_FIXED_MODE_SIZE, 0).require ());
 238   int graphite_expr_type_precision
 239     = 128 <= max_mode_int_precision ?  128 : max_mode_int_precision;
 240   graphite_expr_type
 241     = build_nonstandard_integer_type (graphite_expr_type_precision, 0);
 242 }
 243
 244 /* Return the tree variable that corresponds to the given isl ast identifier
 245    expression (an isl_ast_expr of type isl_ast_expr_id).
 246
 247    FIXME: We should replace blind conversion of id's type with derivation
 248    of the optimal type when we get the corresponding isl support.  Blindly
 249    converting type sizes may be problematic when we switch to smaller
 250    types.  */
 251
 252 tree translate_isl_ast_to_gimple::
 253 gcc_expression_from_isl_ast_expr_id (tree type,
 254                                      __isl_take isl_ast_expr *expr_id,
 255                                      ivs_params &ip)
 256 {
 257   gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
 258   isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
 259   std::map<isl_id *, tree>::iterator res;
 260   res = ip.find (tmp_isl_id);
 261   isl_id_free (tmp_isl_id);
 262   gcc_assert (res != ip.end () &&
 263               "Could not map isl_id to tree expression");
 264   isl_ast_expr_free (expr_id);
 265   tree t = res->second;
 266   if (useless_type_conversion_p (type, TREE_TYPE (t)))
 267     return t;
 268   return fold_convert (type, t);
 269 }
 270
 271 /* Converts an isl_ast_expr_int expression E to a widest_int.
 272    Raises a code generation error when the constant doesn't fit.  */
 273
 274 widest_int translate_isl_ast_to_gimple::
 275 widest_int_from_isl_expr_int (__isl_keep isl_ast_expr *expr)
 276 {
 277   gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
 278   isl_val *val = isl_ast_expr_get_val (expr);
 279   size_t n = isl_val_n_abs_num_chunks (val, sizeof (HOST_WIDE_INT));
 280   HOST_WIDE_INT *chunks = XALLOCAVEC (HOST_WIDE_INT, n);
 281   if (n > WIDE_INT_MAX_ELTS
 282       || isl_val_get_abs_num_chunks (val, sizeof (HOST_WIDE_INT), chunks) == -1)
 283     {
 284       isl_val_free (val);
 285       set_codegen_error ();
 286       return 0;
 287     }
 288   widest_int wi = widest_int::from_array (chunks, n, true);
 289   if (isl_val_is_neg (val))
 290     wi = -wi;
 291   isl_val_free (val);
 292   return wi;
 293 }
 294
 295 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
 296    type TYPE.  Raises a code generation error when the constant doesn't fit.  */
 297
 298 tree translate_isl_ast_to_gimple::
 299 gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr)
 300 {
 301   widest_int wi = widest_int_from_isl_expr_int (expr);
 302   isl_ast_expr_free (expr);
 303   if (codegen_error_p ())
 304     return NULL_TREE;
 305   if (wi::min_precision (wi, TYPE_SIGN (type)) > TYPE_PRECISION (type))
 306     {
 307       set_codegen_error ();
 308       return NULL_TREE;
 309     }
 310   return wide_int_to_tree (type, wi);
 311 }
 312
 313 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
 314    type TYPE.  */
 315
 316 tree translate_isl_ast_to_gimple::
 317 binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
 318 {
 319   enum isl_ast_op_type expr_type = isl_ast_expr_get_op_type (expr);
 320   isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
 321   tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
 322   arg_expr = isl_ast_expr_get_op_arg (expr, 1);
 323   isl_ast_expr_free (expr);
 324
 325   /* From our constraint generation we may get modulo operations that
 326      we cannot represent explicitely but that are no-ops for TYPE.
 327      Elide those.  */
 328   if (expr_type == isl_ast_op_pdiv_r
 329       && isl_ast_expr_get_type (arg_expr) == isl_ast_expr_int
 330       && (wi::exact_log2 (widest_int_from_isl_expr_int (arg_expr))
 331           >= TYPE_PRECISION (type)))
 332     {
 333       isl_ast_expr_free (arg_expr);
 334       return tree_lhs_expr;
 335     }
 336
 337   tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
 338   if (codegen_error_p ())
 339     return NULL_TREE;
 340
 341   switch (expr_type)
 342     {
 343     case isl_ast_op_add:
 344       return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 345
 346     case isl_ast_op_sub:
 347       return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 348
 349     case isl_ast_op_mul:
 350       return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 351
 352     case isl_ast_op_div:
 353       return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 354
 355     case isl_ast_op_pdiv_q:
 356       return fold_build2 (TRUNC_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 357
 358     case isl_ast_op_zdiv_r:
 359     case isl_ast_op_pdiv_r:
 360       return fold_build2 (TRUNC_MOD_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 361
 362     case isl_ast_op_fdiv_q:
 363       return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 364
 365     case isl_ast_op_and:
 366       return fold_build2 (TRUTH_ANDIF_EXPR, type,
 367                           tree_lhs_expr, tree_rhs_expr);
 368
 369     case isl_ast_op_or:
 370       return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 371
 372     case isl_ast_op_eq:
 373       return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 374
 375     case isl_ast_op_le:
 376       return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 377
 378     case isl_ast_op_lt:
 379       return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 380
 381     case isl_ast_op_ge:
 382       return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 383
 384     case isl_ast_op_gt:
 385       return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
 386
 387     default:
 388       gcc_unreachable ();
 389     }
 390 }
 391
 392 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
 393    type TYPE.  */
 394
 395 tree translate_isl_ast_to_gimple::
 396 ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
 397 {
 398   enum isl_ast_op_type t = isl_ast_expr_get_op_type (expr);
 399   gcc_assert (t == isl_ast_op_cond || t == isl_ast_op_select);
 400   isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
 401   tree a = gcc_expression_from_isl_expression (type, arg_expr, ip);
 402   arg_expr = isl_ast_expr_get_op_arg (expr, 1);
 403   tree b = gcc_expression_from_isl_expression (type, arg_expr, ip);
 404   arg_expr = isl_ast_expr_get_op_arg (expr, 2);
 405   tree c = gcc_expression_from_isl_expression (type, arg_expr, ip);
 406   isl_ast_expr_free (expr);
 407
 408   if (codegen_error_p ())
 409     return NULL_TREE;
 410
 411   return fold_build3 (COND_EXPR, type, a, b, c);
 412 }
 413
 414 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
 415    type TYPE.  */
 416
 417 tree translate_isl_ast_to_gimple::
 418 unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
 419 {
 420   gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
 421   isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
 422   tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
 423   isl_ast_expr_free (expr);
 424   return codegen_error_p () ? NULL_TREE
 425     : fold_build1 (NEGATE_EXPR, type, tree_expr);
 426 }
 427
 428 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
 429    to a GCC expression tree of type TYPE.  */
 430
 431 tree translate_isl_ast_to_gimple::
 432 nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
 433 {
 434   enum tree_code op_code;
 435   switch (isl_ast_expr_get_op_type (expr))
 436     {
 437     case isl_ast_op_max:
 438       op_code = MAX_EXPR;
 439       break;
 440
 441     case isl_ast_op_min:
 442       op_code = MIN_EXPR;
 443       break;
 444
 445     default:
 446       gcc_unreachable ();
 447     }
 448   isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
 449   tree res = gcc_expression_from_isl_expression (type, arg_expr, ip);
 450
 451   if (codegen_error_p ())
 452     {
 453       isl_ast_expr_free (expr);
 454       return NULL_TREE;
 455     }
 456
 457   int i;
 458   for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
 459     {
 460       arg_expr = isl_ast_expr_get_op_arg (expr, i);
 461       tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
 462
 463       if (codegen_error_p ())
 464         {
 465           isl_ast_expr_free (expr);
 466           return NULL_TREE;
 467         }
 468
 469       res = fold_build2 (op_code, type, res, t);
 470     }
 471   isl_ast_expr_free (expr);
 472   return res;
 473 }
 474
 475 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
 476    type TYPE.  */
 477
 478 tree translate_isl_ast_to_gimple::
 479 gcc_expression_from_isl_expr_op (tree type, __isl_take isl_ast_expr *expr,
 480                                  ivs_params &ip)
 481 {
 482   if (codegen_error_p ())
 483     {
 484       isl_ast_expr_free (expr);
 485       return NULL_TREE;
 486     }
 487
 488   gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
 489   switch (isl_ast_expr_get_op_type (expr))
 490     {
 491     /* These isl ast expressions are not supported yet.  */
 492     case isl_ast_op_error:
 493     case isl_ast_op_call:
 494     case isl_ast_op_and_then:
 495     case isl_ast_op_or_else:
 496       gcc_unreachable ();
 497
 498     case isl_ast_op_max:
 499     case isl_ast_op_min:
 500       return nary_op_to_tree (type, expr, ip);
 501
 502     case isl_ast_op_add:
 503     case isl_ast_op_sub:
 504     case isl_ast_op_mul:
 505     case isl_ast_op_div:
 506     case isl_ast_op_pdiv_q:
 507     case isl_ast_op_pdiv_r:
 508     case isl_ast_op_fdiv_q:
 509     case isl_ast_op_zdiv_r:
 510     case isl_ast_op_and:
 511     case isl_ast_op_or:
 512     case isl_ast_op_eq:
 513     case isl_ast_op_le:
 514     case isl_ast_op_lt:
 515     case isl_ast_op_ge:
 516     case isl_ast_op_gt:
 517       return binary_op_to_tree (type, expr, ip);
 518
 519     case isl_ast_op_minus:
 520       return unary_op_to_tree (type, expr, ip);
 521
 522     case isl_ast_op_cond:
 523     case isl_ast_op_select:
 524       return ternary_op_to_tree (type, expr, ip);
 525
 526     default:
 527       gcc_unreachable ();
 528     }
 529
 530   return NULL_TREE;
 531 }
 532
 533 /* Converts an isl AST expression E back to a GCC expression tree of
 534    type TYPE.  */
 535
 536 tree translate_isl_ast_to_gimple::
 537 gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *expr,
 538                                     ivs_params &ip)
 539 {
 540   if (codegen_error_p ())
 541     {
 542       isl_ast_expr_free (expr);
 543       return NULL_TREE;
 544     }
 545
 546   switch (isl_ast_expr_get_type (expr))
 547     {
 548     case isl_ast_expr_id:
 549       return gcc_expression_from_isl_ast_expr_id (type, expr, ip);
 550
 551     case isl_ast_expr_int:
 552       return gcc_expression_from_isl_expr_int (type, expr);
 553
 554     case isl_ast_expr_op:
 555       return gcc_expression_from_isl_expr_op (type, expr, ip);
 556
 557     default:
 558       gcc_unreachable ();
 559     }
 560
 561   return NULL_TREE;
 562 }
 563
 564 /* Creates a new LOOP corresponding to isl_ast_node_for.  Inserts an
 565    induction variable for the new LOOP.  New LOOP is attached to CFG
 566    starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
 567    becomes the child loop of the OUTER_LOOP.  NEWIVS_INDEX binds
 568    isl's scattering name to the induction variable created for the
 569    loop of STMT.  The new induction variable is inserted in the NEWIVS
 570    vector and is of type TYPE.  */
 571
 572 struct loop *translate_isl_ast_to_gimple::
 573 graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for,
 574                           loop_p outer, tree type, tree lb, tree ub,
 575                           ivs_params &ip)
 576 {
 577   isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
 578   tree stride = gcc_expression_from_isl_expression (type, for_inc, ip);
 579
 580   /* To fail code generation, we generate wrong code until we discard it.  */
 581   if (codegen_error_p ())
 582     stride = integer_zero_node;
 583
 584   tree ivvar = create_tmp_var (type, "graphite_IV");
 585   tree iv, iv_after_increment;
 586   loop_p loop = create_empty_loop_on_edge
 587     (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
 588      outer ? outer : entry_edge->src->loop_father);
 589
 590   isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
 591   isl_id *id = isl_ast_expr_get_id (for_iterator);
 592   std::map<isl_id *, tree>::iterator res;
 593   res = ip.find (id);
 594   if (ip.count (id))
 595     isl_id_free (res->first);
 596   ip[id] = iv;
 597   isl_ast_expr_free (for_iterator);
 598   return loop;
 599 }
 600
 601 /* Create the loop for a isl_ast_node_for.
 602
 603    - NEXT_E is the edge where new generated code should be attached.  */
 604
 605 edge translate_isl_ast_to_gimple::
 606 translate_isl_ast_for_loop (loop_p context_loop,
 607                             __isl_keep isl_ast_node *node_for, edge next_e,
 608                             tree type, tree lb, tree ub,
 609                             ivs_params &ip)
 610 {
 611   gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
 612   struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
 613                                                 type, lb, ub, ip);
 614   edge last_e = single_exit (loop);
 615   edge to_body = single_succ_edge (loop->header);
 616   basic_block after = to_body->dest;
 617
 618   /* Translate the body of the loop.  */
 619   isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
 620   next_e = translate_isl_ast (loop, for_body, to_body, ip);
 621   isl_ast_node_free (for_body);
 622
 623   /* Early return if we failed to translate loop body.  */
 624   if (!next_e || codegen_error_p ())
 625     return NULL;
 626
 627   if (next_e->dest != after)
 628     redirect_edge_succ_nodup (next_e, after);
 629   set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
 630
 631   if (flag_loop_parallelize_all)
 632     {
 633       isl_id *id = isl_ast_node_get_annotation (node_for);
 634       gcc_assert (id);
 635       ast_build_info *for_info = (ast_build_info *) isl_id_get_user (id);
 636       loop->can_be_parallel = for_info->is_parallelizable;
 637       free (for_info);
 638       isl_id_free (id);
 639     }
 640
 641   return last_e;
 642 }
 643
 644 /* We use this function to get the upper bound because of the form,
 645    which is used by isl to represent loops:
 646
 647    for (iterator = init; cond; iterator += inc)
 648
 649    {
 650
 651    ...
 652
 653    }
 654
 655    The loop condition is an arbitrary expression, which contains the
 656    current loop iterator.
 657
 658    (e.g. iterator + 3 < B && C > iterator + A)
 659
 660    We have to know the upper bound of the iterator to generate a loop
 661    in Gimple form. It can be obtained from the special representation
 662    of the loop condition, which is generated by isl,
 663    if the ast_build_atomic_upper_bound option is set. In this case,
 664    isl generates a loop condition that consists of the current loop
 665    iterator, + an operator (< or <=) and an expression not involving
 666    the iterator, which is processed and returned by this function.
 667
 668    (e.g iterator <= upper-bound-expression-without-iterator)  */
 669
 670 static __isl_give isl_ast_expr *
 671 get_upper_bound (__isl_keep isl_ast_node *node_for)
 672 {
 673   gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
 674   isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
 675   gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
 676   isl_ast_expr *res;
 677   switch (isl_ast_expr_get_op_type (for_cond))
 678     {
 679     case isl_ast_op_le:
 680       res = isl_ast_expr_get_op_arg (for_cond, 1);
 681       break;
 682
 683     case isl_ast_op_lt:
 684       {
 685         /* (iterator < ub) => (iterator <= ub - 1).  */
 686         isl_val *one =
 687           isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
 688         isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
 689         res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
 690         break;
 691       }
 692
 693     default:
 694       gcc_unreachable ();
 695     }
 696   isl_ast_expr_free (for_cond);
 697   return res;
 698 }
 699
 700 /* Translates an isl_ast_node_for to Gimple. */
 701
 702 edge translate_isl_ast_to_gimple::
 703 translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node,
 704                             edge next_e, ivs_params &ip)
 705 {
 706   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for);
 707   tree type = graphite_expr_type;
 708
 709   isl_ast_expr *for_init = isl_ast_node_for_get_init (node);
 710   tree lb = gcc_expression_from_isl_expression (type, for_init, ip);
 711   /* To fail code generation, we generate wrong code until we discard it.  */
 712   if (codegen_error_p ())
 713     lb = integer_zero_node;
 714
 715   isl_ast_expr *upper_bound = get_upper_bound (node);
 716   tree ub = gcc_expression_from_isl_expression (type, upper_bound, ip);
 717   /* To fail code generation, we generate wrong code until we discard it.  */
 718   if (codegen_error_p ())
 719     ub = integer_zero_node;
 720
 721   edge last_e = single_succ_edge (split_edge (next_e));
 722   translate_isl_ast_for_loop (context_loop, node, next_e,
 723                               type, lb, ub, ip);
 724   return last_e;
 725 }
 726
 727 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
 728    variables of the loops around GBB in SESE.
 729
 730    FIXME: Instead of using a vec<tree> that maps each loop id to a possible
 731    chrec, we could consider using a map<int, tree> that maps loop ids to the
 732    corresponding tree expressions.  */
 733
 734 void translate_isl_ast_to_gimple::
 735 build_iv_mapping (vec<tree> iv_map, gimple_poly_bb_p gbb,
 736                   __isl_keep isl_ast_expr *user_expr, ivs_params &ip,
 737                   sese_l &region)
 738 {
 739   gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op &&
 740               isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call);
 741   int i;
 742   isl_ast_expr *arg_expr;
 743   for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++)
 744     {
 745       arg_expr = isl_ast_expr_get_op_arg (user_expr, i);
 746       tree type = graphite_expr_type;
 747       tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
 748
 749       /* To fail code generation, we generate wrong code until we discard it.  */
 750       if (codegen_error_p ())
 751         t = integer_zero_node;
 752
 753       loop_p old_loop = gbb_loop_at_index (gbb, region, i - 1);
 754       iv_map[old_loop->num] = t;
 755     }
 756 }
 757
 758 /* Translates an isl_ast_node_user to Gimple.
 759
 760    FIXME: We should remove iv_map.create (loop->num + 1), if it is possible.  */
 761
 762 edge translate_isl_ast_to_gimple::
 763 translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
 764                              edge next_e, ivs_params &ip)
 765 {
 766   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user);
 767
 768   isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node);
 769   isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0);
 770   gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id);
 771
 772   isl_id *name_id = isl_ast_expr_get_id (name_expr);
 773   poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id);
 774   gcc_assert (pbb);
 775
 776   gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
 777
 778   isl_ast_expr_free (name_expr);
 779   isl_id_free (name_id);
 780
 781   gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
 782               "The entry block should not even appear within a scop");
 783
 784   const int nb_loops = number_of_loops (cfun);
 785   vec<tree> iv_map;
 786   iv_map.create (nb_loops);
 787   iv_map.safe_grow_cleared (nb_loops);
 788
 789   build_iv_mapping (iv_map, gbb, user_expr, ip, pbb->scop->scop_info->region);
 790   isl_ast_expr_free (user_expr);
 791
 792   basic_block old_bb = GBB_BB (gbb);
 793   if (dump_file)
 794     {
 795       fprintf (dump_file,
 796                "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
 797                old_bb->index, next_e->src->index, next_e->dest->index);
 798       print_loops_bb (dump_file, GBB_BB (gbb), 0, 3);
 799
 800     }
 801
 802   next_e = copy_bb_and_scalar_dependences (old_bb, next_e, iv_map);
 803
 804   iv_map.release ();
 805
 806   if (codegen_error_p ())
 807     return NULL;
 808
 809   if (dump_file)
 810     {
 811       fprintf (dump_file, "[codegen] (after copy) new basic block\n");
 812       print_loops_bb (dump_file, next_e->src, 0, 3);
 813     }
 814
 815   return next_e;
 816 }
 817
 818 /* Translates an isl_ast_node_block to Gimple. */
 819
 820 edge translate_isl_ast_to_gimple::
 821 translate_isl_ast_node_block (loop_p context_loop,
 822                               __isl_keep isl_ast_node *node,
 823                               edge next_e, ivs_params &ip)
 824 {
 825   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_block);
 826   isl_ast_node_list *node_list = isl_ast_node_block_get_children (node);
 827   int i;
 828   for (i = 0; i < isl_ast_node_list_n_ast_node (node_list); i++)
 829     {
 830       isl_ast_node *tmp_node = isl_ast_node_list_get_ast_node (node_list, i);
 831       next_e = translate_isl_ast (context_loop, tmp_node, next_e, ip);
 832       isl_ast_node_free (tmp_node);
 833     }
 834   isl_ast_node_list_free (node_list);
 835   return next_e;
 836 }
 837
 838 /* Creates a new if region corresponding to isl's cond.  */
 839
 840 edge 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 = graphite_expr_type;
 845   tree cond_expr = gcc_expression_from_isl_expression (type, if_cond, ip);
 846
 847   /* To fail code generation, we generate wrong code until we discard it.  */
 848   if (codegen_error_p ())
 849     cond_expr = integer_zero_node;
 850
 851   edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
 852   return exit_edge;
 853 }
 854
 855 /* Translates an isl_ast_node_if to Gimple.  */
 856
 857 edge translate_isl_ast_to_gimple::
 858 translate_isl_ast_node_if (loop_p context_loop,
 859                            __isl_keep isl_ast_node *node,
 860                            edge next_e, ivs_params &ip)
 861 {
 862   gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_if);
 863   isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node);
 864   edge last_e = graphite_create_new_guard (next_e, if_cond, ip);
 865   edge true_e = get_true_edge_from_guard_bb (next_e->dest);
 866   merge_points.safe_push (last_e);
 867
 868   isl_ast_node *then_node = isl_ast_node_if_get_then (node);
 869   translate_isl_ast (context_loop, then_node, true_e, ip);
 870   isl_ast_node_free (then_node);
 871
 872   edge false_e = get_false_edge_from_guard_bb (next_e->dest);
 873   isl_ast_node *else_node = isl_ast_node_if_get_else (node);
 874   if (isl_ast_node_get_type (else_node) != isl_ast_node_error)
 875     translate_isl_ast (context_loop, else_node, false_e, ip);
 876
 877   isl_ast_node_free (else_node);
 878   return last_e;
 879 }
 880
 881 /* Translates an isl AST node NODE to GCC representation in the
 882    context of a SESE.  */
 883
 884 edge translate_isl_ast_to_gimple::
 885 translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
 886                    edge next_e, ivs_params &ip)
 887 {
 888   if (codegen_error_p ())
 889     return NULL;
 890
 891   switch (isl_ast_node_get_type (node))
 892     {
 893     case isl_ast_node_error:
 894       gcc_unreachable ();
 895
 896     case isl_ast_node_for:
 897       return translate_isl_ast_node_for (context_loop, node,
 898                                          next_e, ip);
 899
 900     case isl_ast_node_if:
 901       return translate_isl_ast_node_if (context_loop, node,
 902                                         next_e, ip);
 903
 904     case isl_ast_node_user:
 905       return translate_isl_ast_node_user (node, next_e, ip);
 906
 907     case isl_ast_node_block:
 908       return translate_isl_ast_node_block (context_loop, node,
 909                                            next_e, ip);
 910
 911     case isl_ast_node_mark:
 912       {
 913         isl_ast_node *n = isl_ast_node_mark_get_node (node);
 914         edge e = translate_isl_ast (context_loop, n, next_e, ip);
 915         isl_ast_node_free (n);
 916         return e;
 917       }
 918
 919     default:
 920       gcc_unreachable ();
 921     }
 922 }
 923
 924 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
 925    When OLD_NAME and EXPR are the same we assert.  */
 926
 927 void translate_isl_ast_to_gimple::
 928 set_rename (tree old_name, tree expr)
 929 {
 930   if (dump_file)
 931     {
 932       fprintf (dump_file, "[codegen] setting rename: old_name = ");
 933       print_generic_expr (dump_file, old_name);
 934       fprintf (dump_file, ", new decl = ");
 935       print_generic_expr (dump_file, expr);
 936       fprintf (dump_file, "\n");
 937     }
 938   bool res = region->rename_map->put (old_name, expr);
 939   gcc_assert (! res);
 940 }
 941
 942 /* Return an iterator to the instructions comes last in the execution order.
 943    Either GSI1 and GSI2 should belong to the same basic block or one of their
 944    respective basic blocks should dominate the other.  */
 945
 946 gimple_stmt_iterator
 947 later_of_the_two (gimple_stmt_iterator gsi1, gimple_stmt_iterator gsi2)
 948 {
 949   basic_block bb1 = gsi_bb (gsi1);
 950   basic_block bb2 = gsi_bb (gsi2);
 951
 952   /* Find the iterator which is the latest.  */
 953   if (bb1 == bb2)
 954     {
 955       gimple *stmt1 = gsi_stmt (gsi1);
 956       gimple *stmt2 = gsi_stmt (gsi2);
 957
 958       if (stmt1 != NULL && stmt2 != NULL)
 959         {
 960           bool is_phi1 = gimple_code (stmt1) == GIMPLE_PHI;
 961           bool is_phi2 = gimple_code (stmt2) == GIMPLE_PHI;
 962
 963           if (is_phi1 != is_phi2)
 964             return is_phi1 ? gsi2 : gsi1;
 965         }
 966
 967       /* For empty basic blocks gsis point to the end of the sequence.  Since
 968          there is no operator== defined for gimple_stmt_iterator and for gsis
 969          not pointing to a valid statement gsi_next would assert.  */
 970       gimple_stmt_iterator gsi = gsi1;
 971       do {
 972         if (gsi_stmt (gsi) == gsi_stmt (gsi2))
 973           return gsi2;
 974         gsi_next (&gsi);
 975       } while (!gsi_end_p (gsi));
 976
 977       return gsi1;
 978     }
 979
 980   /* Find the basic block closest to the basic block which defines stmt.  */
 981   if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
 982     return gsi1;
 983
 984   gcc_assert (dominated_by_p (CDI_DOMINATORS, bb2, bb1));
 985   return gsi2;
 986 }
 987
 988 /* Insert each statement from SEQ at its earliest insertion p.  */
 989
 990 void translate_isl_ast_to_gimple::
 991 gsi_insert_earliest (gimple_seq seq)
 992 {
 993   update_modified_stmts (seq);
 994   sese_l &codegen_region = region->if_region->true_region->region;
 995   basic_block begin_bb = get_entry_bb (codegen_region);
 996
 997   /* Inserting the gimple statements in a vector because gimple_seq behave
 998      in strage ways when inserting the stmts from it into different basic
 999      blocks one at a time.  */
1000   auto_vec<gimple *, 3> stmts;
1001   for (gimple_stmt_iterator gsi = gsi_start (seq); !gsi_end_p (gsi);
1002        gsi_next (&gsi))
1003     stmts.safe_push (gsi_stmt (gsi));
1004
1005   int i;
1006   gimple *use_stmt;
1007   FOR_EACH_VEC_ELT (stmts, i, use_stmt)
1008     {
1009       gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
1010       gimple_stmt_iterator gsi_def_stmt = gsi_start_bb_nondebug (begin_bb);
1011
1012       use_operand_p use_p;
1013       ssa_op_iter op_iter;
1014       FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, op_iter, SSA_OP_USE)
1015         {
1016           /* Iterator to the current def of use_p.  For function parameters or
1017              anything where def is not found, insert at the beginning of the
1018              generated region.  */
1019           gimple_stmt_iterator gsi_stmt = gsi_def_stmt;
1020
1021           tree op = USE_FROM_PTR (use_p);
1022           gimple *stmt = SSA_NAME_DEF_STMT (op);
1023           if (stmt && (gimple_code (stmt) != GIMPLE_NOP))
1024             gsi_stmt = gsi_for_stmt (stmt);
1025
1026           /* For region parameters, insert at the beginning of the generated
1027              region.  */
1028           if (!bb_in_sese_p (gsi_bb (gsi_stmt), codegen_region))
1029             gsi_stmt = gsi_def_stmt;
1030
1031           gsi_def_stmt = later_of_the_two (gsi_stmt, gsi_def_stmt);
1032         }
1033
1034       if (!gsi_stmt (gsi_def_stmt))
1035         {
1036           gimple_stmt_iterator gsi = gsi_after_labels (gsi_bb (gsi_def_stmt));
1037           gsi_insert_before (&gsi, use_stmt, GSI_NEW_STMT);
1038         }
1039       else if (gimple_code (gsi_stmt (gsi_def_stmt)) == GIMPLE_PHI)
1040         {
1041           gimple_stmt_iterator bsi
1042             = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt));
1043           /* Insert right after the PHI statements.  */
1044           gsi_insert_before (&bsi, use_stmt, GSI_NEW_STMT);
1045         }
1046       else
1047         gsi_insert_after (&gsi_def_stmt, use_stmt, GSI_NEW_STMT);
1048
1049       if (dump_file)
1050         {
1051           fprintf (dump_file, "[codegen] inserting statement: ");
1052           print_gimple_stmt (dump_file, use_stmt, 0, TDF_VOPS | TDF_MEMSYMS);
1053           print_loops_bb (dump_file, gimple_bb (use_stmt), 0, 3);
1054         }
1055     }
1056 }
1057
1058 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1059    scalar evolution around LOOP.  */
1060
1061 tree translate_isl_ast_to_gimple::
1062 get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop,
1063                       vec<tree> iv_map)
1064 {
1065   tree scev = scalar_evolution_in_region (region->region, loop, old_name);
1066
1067   /* At this point we should know the exact scev for each
1068      scalar SSA_NAME used in the scop: all the other scalar
1069      SSA_NAMEs should have been translated out of SSA using
1070      arrays with one element.  */
1071   tree new_expr;
1072   if (chrec_contains_undetermined (scev))
1073     {
1074       set_codegen_error ();
1075       return build_zero_cst (TREE_TYPE (old_name));
1076     }
1077
1078   new_expr = chrec_apply_map (scev, iv_map);
1079
1080   /* The apply should produce an expression tree containing
1081      the uses of the new induction variables.  We should be
1082      able to use new_expr instead of the old_name in the newly
1083      generated loop nest.  */
1084   if (chrec_contains_undetermined (new_expr)
1085       || tree_contains_chrecs (new_expr, NULL))
1086     {
1087       set_codegen_error ();
1088       return build_zero_cst (TREE_TYPE (old_name));
1089     }
1090
1091   /* Replace the old_name with the new_expr.  */
1092   return force_gimple_operand (unshare_expr (new_expr), stmts,
1093                                true, NULL_TREE);
1094 }
1095
1096
1097 /* Return true if STMT should be copied from region to the new code-generated
1098    region.  LABELs, CONDITIONS, induction-variables and region parameters need
1099    not be copied.  */
1100
1101 static bool
1102 should_copy_to_new_region (gimple *stmt, sese_info_p region)
1103 {
1104   /* Do not copy labels or conditions.  */
1105   if (gimple_code (stmt) == GIMPLE_LABEL
1106       || gimple_code (stmt) == GIMPLE_COND)
1107     return false;
1108
1109   tree lhs;
1110   /* Do not copy induction variables.  */
1111   if (is_gimple_assign (stmt)
1112       && (lhs = gimple_assign_lhs (stmt))
1113       && TREE_CODE (lhs) == SSA_NAME
1114       && is_gimple_reg (lhs)
1115       && scev_analyzable_p (lhs, region->region))
1116     return false;
1117
1118   return true;
1119 }
1120
1121 /* Duplicates the statements of basic block BB into basic block NEW_BB
1122    and compute the new induction variables according to the IV_MAP.  */
1123
1124 bool translate_isl_ast_to_gimple::
1125 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
1126                                 vec<tree> iv_map)
1127 {
1128   /* Iterator poining to the place where new statement (s) will be inserted.  */
1129   gimple_stmt_iterator gsi_tgt = gsi_last_bb (new_bb);
1130
1131   for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1132        gsi_next (&gsi))
1133     {
1134       gimple *stmt = gsi_stmt (gsi);
1135       if (!should_copy_to_new_region (stmt, region))
1136         continue;
1137
1138       /* Create a new copy of STMT and duplicate STMT's virtual
1139          operands.  */
1140       gimple *copy = gimple_copy (stmt);
1141       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
1142
1143       /* Rather than not copying debug stmts we reset them.
1144          ???  Where we can rewrite uses without inserting new
1145          stmts we could simply do that.  */
1146       if (is_gimple_debug (copy))
1147         {
1148           if (gimple_debug_bind_p (copy))
1149             gimple_debug_bind_reset_value (copy);
1150           else if (gimple_debug_source_bind_p (copy))
1151             ;
1152           else
1153             gcc_unreachable ();
1154         }
1155
1156       if (dump_file)
1157         {
1158           fprintf (dump_file, "[codegen] inserting statement: ");
1159           print_gimple_stmt (dump_file, copy, 0);
1160         }
1161
1162       maybe_duplicate_eh_stmt (copy, stmt);
1163       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
1164
1165       /* Crete new names for each def in the copied stmt.  */
1166       def_operand_p def_p;
1167       ssa_op_iter op_iter;
1168       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
1169         {
1170           tree old_name = DEF_FROM_PTR (def_p);
1171           create_new_def_for (old_name, copy, def_p);
1172         }
1173
1174       if (codegen_error_p ())
1175         return false;
1176
1177       /* For each SCEV analyzable SSA_NAME, rename their usage.  */
1178       ssa_op_iter iter;
1179       use_operand_p use_p;
1180       if (!is_gimple_debug (copy))
1181         FOR_EACH_SSA_USE_OPERAND (use_p, copy, iter, SSA_OP_USE)
1182           {
1183             tree old_name = USE_FROM_PTR (use_p);
1184
1185             if (TREE_CODE (old_name) != SSA_NAME
1186                 || SSA_NAME_IS_DEFAULT_DEF (old_name)
1187                 || ! scev_analyzable_p (old_name, region->region))
1188               continue;
1189
1190             gimple_seq stmts = NULL;
1191             tree new_name = get_rename_from_scev (old_name, &stmts,
1192                                                   bb->loop_father, iv_map);
1193             if (! codegen_error_p ())
1194               gsi_insert_earliest (stmts);
1195             replace_exp (use_p, new_name);
1196           }
1197
1198       update_stmt (copy);
1199     }
1200
1201   return true;
1202 }
1203
1204
1205 /* Copies BB and includes in the copied BB all the statements that can
1206    be reached following the use-def chains from the memory accesses,
1207    and returns the next edge following this new block.  */
1208
1209 edge translate_isl_ast_to_gimple::
1210 copy_bb_and_scalar_dependences (basic_block bb, edge next_e, vec<tree> iv_map)
1211 {
1212   basic_block new_bb = split_edge (next_e);
1213   gimple_stmt_iterator gsi_tgt = gsi_last_bb (new_bb);
1214   for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1215        gsi_next (&psi))
1216     {
1217       gphi *phi = psi.phi ();
1218       tree res = gimple_phi_result (phi);
1219       if (virtual_operand_p (res)
1220           || scev_analyzable_p (res, region->region))
1221         continue;
1222
1223       tree new_phi_def;
1224       tree *rename = region->rename_map->get (res);
1225       if (! rename)
1226         {
1227           new_phi_def = create_tmp_reg (TREE_TYPE (res));
1228           set_rename (res, new_phi_def);
1229         }
1230       else
1231         new_phi_def = *rename;
1232
1233       gassign *ass = gimple_build_assign (NULL_TREE, new_phi_def);
1234       create_new_def_for (res, ass, NULL);
1235       gsi_insert_after (&gsi_tgt, ass, GSI_NEW_STMT);
1236     }
1237
1238   if (!graphite_copy_stmts_from_block (bb, new_bb, iv_map))
1239     {
1240       set_codegen_error ();
1241       return NULL;
1242     }
1243
1244   /* Insert out-of SSA copies on the original BB outgoing edges.  */
1245   gsi_tgt = gsi_last_bb (new_bb);
1246   basic_block bb_for_succs = bb;
1247   if (bb_for_succs == bb_for_succs->loop_father->latch
1248       && bb_in_sese_p (bb_for_succs, region->region)
1249       && sese_trivially_empty_bb_p (bb_for_succs))
1250     bb_for_succs = NULL;
1251   while (bb_for_succs)
1252     {
1253       basic_block latch = NULL;
1254       edge_iterator ei;
1255       edge e;
1256       FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
1257         {
1258           for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
1259                gsi_next (&psi))
1260             {
1261               gphi *phi = psi.phi ();
1262               tree res = gimple_phi_result (phi);
1263               if (virtual_operand_p (res)
1264                   || scev_analyzable_p (res, region->region))
1265                 continue;
1266
1267               tree new_phi_def;
1268               tree *rename = region->rename_map->get (res);
1269               if (! rename)
1270                 {
1271                   new_phi_def = create_tmp_reg (TREE_TYPE (res));
1272                   set_rename (res, new_phi_def);
1273                 }
1274               else
1275                 new_phi_def = *rename;
1276
1277               tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
1278               if (TREE_CODE (arg) == SSA_NAME
1279                   && scev_analyzable_p (arg, region->region))
1280                 {
1281                   gimple_seq stmts = NULL;
1282                   tree new_name = get_rename_from_scev (arg, &stmts,
1283                                                         bb->loop_father,
1284                                                         iv_map);
1285                   if (! codegen_error_p ())
1286                     gsi_insert_earliest (stmts);
1287                   arg = new_name;
1288                 }
1289               gassign *ass = gimple_build_assign (new_phi_def, arg);
1290               gsi_insert_after (&gsi_tgt, ass, GSI_NEW_STMT);
1291             }
1292           if (e->dest == bb_for_succs->loop_father->latch
1293               && bb_in_sese_p (e->dest, region->region)
1294               && sese_trivially_empty_bb_p (e->dest))
1295             latch = e->dest;
1296         }
1297       bb_for_succs = latch;
1298     }
1299
1300   return single_succ_edge (new_bb);
1301 }
1302
1303 /* Add isl's parameter identifiers and corresponding trees to ivs_params.  */
1304
1305 void translate_isl_ast_to_gimple::
1306 add_parameters_to_ivs_params (scop_p scop, ivs_params &ip)
1307 {
1308   sese_info_p region = scop->scop_info;
1309   unsigned nb_parameters = isl_set_dim (scop->param_context, isl_dim_param);
1310   gcc_assert (nb_parameters == sese_nb_params (region));
1311   unsigned i;
1312   tree param;
1313   FOR_EACH_VEC_ELT (region->params, i, param)
1314     {
1315       isl_id *tmp_id = isl_set_get_dim_id (scop->param_context,
1316                                            isl_dim_param, i);
1317       ip[tmp_id] = param;
1318     }
1319 }
1320
1321
1322 /* Generates a build, which specifies the constraints on the parameters.  */
1323
1324 __isl_give isl_ast_build *translate_isl_ast_to_gimple::
1325 generate_isl_context (scop_p scop)
1326 {
1327   isl_set *context_isl = isl_set_params (isl_set_copy (scop->param_context));
1328   return isl_ast_build_from_context (context_isl);
1329 }
1330
1331 /* This method is executed before the construction of a for node.  */
1332 __isl_give isl_id *
1333 ast_build_before_for (__isl_keep isl_ast_build *build, void *user)
1334 {
1335   isl_union_map *dependences = (isl_union_map *) user;
1336   ast_build_info *for_info = XNEW (struct ast_build_info);
1337   isl_union_map *schedule = isl_ast_build_get_schedule (build);
1338   isl_space *schedule_space = isl_ast_build_get_schedule_space (build);
1339   int dimension = isl_space_dim (schedule_space, isl_dim_out);
1340   for_info->is_parallelizable =
1341     !carries_deps (schedule, dependences, dimension);
1342   isl_union_map_free (schedule);
1343   isl_space_free (schedule_space);
1344   isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info);
1345   return id;
1346 }
1347
1348 /* Generate isl AST from schedule of SCOP.  */
1349
1350 __isl_give isl_ast_node *translate_isl_ast_to_gimple::
1351 scop_to_isl_ast (scop_p scop)
1352 {
1353   gcc_assert (scop->transformed_schedule);
1354
1355   /* Set the separate option to reduce control flow overhead.  */
1356   isl_schedule *schedule = isl_schedule_map_schedule_node_bottom_up
1357     (isl_schedule_copy (scop->transformed_schedule), set_separate_option, NULL);
1358   isl_ast_build *context_isl = generate_isl_context (scop);
1359
1360   if (flag_loop_parallelize_all)
1361     {
1362       scop_get_dependences (scop);
1363       context_isl =
1364         isl_ast_build_set_before_each_for (context_isl, ast_build_before_for,
1365                                            scop->dependence);
1366     }
1367
1368   isl_ast_node *ast_isl = isl_ast_build_node_from_schedule
1369     (context_isl, schedule);
1370   isl_ast_build_free (context_isl);
1371   return ast_isl;
1372 }
1373
1374 /* Generate out-of-SSA copies for the entry edge FALSE_ENTRY/TRUE_ENTRY
1375    in REGION.  */
1376
1377 static void
1378 generate_entry_out_of_ssa_copies (edge false_entry,
1379                                   edge true_entry,
1380                                   sese_info_p region)
1381 {
1382   gimple_stmt_iterator gsi_tgt = gsi_start_bb (true_entry->dest);
1383   for (gphi_iterator psi = gsi_start_phis (false_entry->dest);
1384        !gsi_end_p (psi); gsi_next (&psi))
1385     {
1386       gphi *phi = psi.phi ();
1387       tree res = gimple_phi_result (phi);
1388       if (virtual_operand_p (res))
1389         continue;
1390       /* When there's no out-of-SSA var registered do not bother
1391          to create one.  */
1392       tree *rename = region->rename_map->get (res);
1393       if (! rename)
1394         continue;
1395       tree new_phi_def = *rename;
1396       gassign *ass = gimple_build_assign (new_phi_def,
1397                                           PHI_ARG_DEF_FROM_EDGE (phi,
1398                                                                  false_entry));
1399       gsi_insert_after (&gsi_tgt, ass, GSI_NEW_STMT);
1400     }
1401 }
1402
1403 /* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
1404    Return true if code generation succeeded.  */
1405
1406 bool
1407 graphite_regenerate_ast_isl (scop_p scop)
1408 {
1409   sese_info_p region = scop->scop_info;
1410   translate_isl_ast_to_gimple t (region);
1411
1412   ifsese if_region = NULL;
1413   isl_ast_node *root_node;
1414   ivs_params ip;
1415
1416   timevar_push (TV_GRAPHITE_CODE_GEN);
1417   t.add_parameters_to_ivs_params (scop, ip);
1418   root_node = t.scop_to_isl_ast (scop);
1419
1420   if (dump_file && (dump_flags & TDF_DETAILS))
1421     {
1422       fprintf (dump_file, "[scheduler] original schedule:\n");
1423       print_isl_schedule (dump_file, scop->original_schedule);
1424       fprintf (dump_file, "[scheduler] isl transformed schedule:\n");
1425       print_isl_schedule (dump_file, scop->transformed_schedule);
1426
1427       fprintf (dump_file, "[scheduler] original ast:\n");
1428       print_schedule_ast (dump_file, scop->original_schedule, scop);
1429       fprintf (dump_file, "[scheduler] AST generated by isl:\n");
1430       print_isl_ast (dump_file, root_node);
1431     }
1432
1433   if_region = move_sese_in_condition (region);
1434   region->if_region = if_region;
1435
1436   loop_p context_loop = region->region.entry->src->loop_father;
1437   edge e = single_succ_edge (if_region->true_region->region.entry->dest);
1438   basic_block bb = split_edge (e);
1439
1440   /* Update the true_region exit edge.  */
1441   region->if_region->true_region->region.exit = single_succ_edge (bb);
1442
1443   t.translate_isl_ast (context_loop, root_node, e, ip);
1444   if (! t.codegen_error_p ())
1445     {
1446       generate_entry_out_of_ssa_copies (if_region->false_region->region.entry,
1447                                         if_region->true_region->region.entry,
1448                                         region);
1449       sese_insert_phis_for_liveouts (region,
1450                                      if_region->region->region.exit->src,
1451                                      if_region->false_region->region.exit,
1452                                      if_region->true_region->region.exit);
1453       if (dump_file)
1454         fprintf (dump_file, "[codegen] isl AST to Gimple succeeded.\n");
1455     }
1456
1457   if (t.codegen_error_p ())
1458     {
1459       if (dump_file)
1460         fprintf (dump_file, "codegen error: "
1461                  "reverting back to the original code.\n");
1462       set_ifsese_condition (if_region, integer_zero_node);
1463
1464       /* Remove the unreachable region.  */
1465       remove_edge_and_dominated_blocks (if_region->true_region->region.entry);
1466       basic_block ifb = if_region->false_region->region.entry->src;
1467       gimple_stmt_iterator gsi = gsi_last_bb (ifb);
1468       gsi_remove (&gsi, true);
1469       if_region->false_region->region.entry->flags &= ~EDGE_FALSE_VALUE;
1470       if_region->false_region->region.entry->flags |= EDGE_FALLTHRU;
1471       /* remove_edge_and_dominated_blocks marks loops for removal but
1472          doesn't actually remove them (fix that...).  */
1473       loop_p loop;
1474       FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1475         if (! loop->header)
1476           delete_loop (loop);
1477     }
1478
1479   /* We are delaying SSA update to after code-generating all SCOPs.
1480      This is because we analyzed DRs and parameters on the unmodified
1481      IL and thus rely on SSA update to pick up new dominating definitions
1482      from for example SESE liveout PHIs.  This is also for efficiency
1483      as SSA update does work depending on the size of the function.  */
1484
1485   free (if_region->true_region);
1486   free (if_region->region);
1487   free (if_region);
1488
1489   ivs_params_clear (ip);
1490   isl_ast_node_free (root_node);
1491   timevar_pop (TV_GRAPHITE_CODE_GEN);
1492
1493   return !t.codegen_error_p ();
1494 }
1495
1496 #endif  /* HAVE_isl */