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