gcc/graphite-clast-to-gimple.c

   1 /* Translation of CLAST (CLooG AST) to Gimple.
   2    Copyright (C) 2009-2013 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <sebastian.pop@amd.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22
  23 #ifdef HAVE_cloog
  24 #include <isl/set.h>
  25 #include <isl/map.h>
  26 #include <isl/union_map.h>
  27 #include <isl/list.h>
  28 #include <isl/constraint.h>
  29 #include <isl/ilp.h>
  30 #include <isl/aff.h>
  31 #include <cloog/cloog.h>
  32 #include <cloog/isl/domain.h>
  33 #endif
  34
  35 #include "system.h"
  36 #include "coretypes.h"
  37 #include "diagnostic-core.h"
  38 #include "tree-flow.h"
  39 #include "tree-pass.h"
  40 #include "cfgloop.h"
  41 #include "tree-chrec.h"
  42 #include "tree-data-ref.h"
  43 #include "tree-scalar-evolution.h"
  44 #include "sese.h"
  45
  46 #ifdef HAVE_cloog
  47 #include "cloog/cloog.h"
  48 #include "graphite-poly.h"
  49 #include "graphite-clast-to-gimple.h"
  50
  51 typedef const struct clast_expr *clast_name_p;
  52
  53 #ifndef CLOOG_LANGUAGE_C
  54 #define CLOOG_LANGUAGE_C LANGUAGE_C
  55 #endif
  56
  57
  58 /* Converts a GMP constant VAL to a tree and returns it.  */
  59
  60 static tree
  61 gmp_cst_to_tree (tree type, mpz_t val)
  62 {
  63   tree t = type ? type : integer_type_node;
  64   mpz_t tmp;
  65   double_int di;
  66
  67   mpz_init (tmp);
  68   mpz_set (tmp, val);
  69   di = mpz_get_double_int (t, tmp, true);
  70   mpz_clear (tmp);
  71
  72   return double_int_to_tree (t, di);
  73 }
  74
  75 /* Sets RES to the min of V1 and V2.  */
  76
  77 static void
  78 value_min (mpz_t res, mpz_t v1, mpz_t v2)
  79 {
  80   if (mpz_cmp (v1, v2) < 0)
  81     mpz_set (res, v1);
  82   else
  83     mpz_set (res, v2);
  84 }
  85
  86 /* Sets RES to the max of V1 and V2.  */
  87
  88 static void
  89 value_max (mpz_t res, mpz_t v1, mpz_t v2)
  90 {
  91   if (mpz_cmp (v1, v2) < 0)
  92     mpz_set (res, v2);
  93   else
  94     mpz_set (res, v1);
  95 }
  96
  97
  98 /* This flag is set when an error occurred during the translation of
  99    CLAST to Gimple.  */
 100 static bool gloog_error;
 101
 102 /* Verifies properties that GRAPHITE should maintain during translation.  */
 103
 104 static inline void
 105 graphite_verify (void)
 106 {
 107 #ifdef ENABLE_CHECKING
 108   verify_loop_structure ();
 109   verify_loop_closed_ssa (true);
 110 #endif
 111 }
 112
 113 /* Stores the INDEX in a vector and the loop nesting LEVEL for a given
 114    clast NAME.  BOUND_ONE and BOUND_TWO represent the exact lower and
 115    upper bounds that can be inferred from the polyhedral representation.  */
 116
 117 typedef struct clast_name_index {
 118   int index;
 119   int level;
 120   mpz_t bound_one, bound_two;
 121   const char *name;
 122   /* If free_name is set, the content of name was allocated by us and needs
 123      to be freed.  */
 124   char *free_name;
 125 } *clast_name_index_p;
 126
 127 /* Returns a pointer to a new element of type clast_name_index_p built
 128    from NAME, INDEX, LEVEL, BOUND_ONE, and BOUND_TWO.  */
 129
 130 static inline clast_name_index_p
 131 new_clast_name_index (const char *name, int index, int level,
 132                       mpz_t bound_one, mpz_t bound_two)
 133 {
 134   clast_name_index_p res = XNEW (struct clast_name_index);
 135   char *new_name = XNEWVEC (char, strlen (name) + 1);
 136   strcpy (new_name, name);
 137
 138   res->name = new_name;
 139   res->free_name = new_name;
 140   res->level = level;
 141   res->index = index;
 142   mpz_init (res->bound_one);
 143   mpz_init (res->bound_two);
 144   mpz_set (res->bound_one, bound_one);
 145   mpz_set (res->bound_two, bound_two);
 146   return res;
 147 }
 148
 149 /* Free the memory taken by a clast_name_index struct.  */
 150
 151 static void
 152 free_clast_name_index (void *ptr)
 153 {
 154   struct clast_name_index *c = (struct clast_name_index *) ptr;
 155   if (c->free_name)
 156     free (c->free_name);
 157   mpz_clear (c->bound_one);
 158   mpz_clear (c->bound_two);
 159   free (ptr);
 160 }
 161
 162 /* For a given clast NAME, returns -1 if NAME is not in the
 163    INDEX_TABLE, otherwise returns the loop level for the induction
 164    variable NAME, or if it is a parameter, the parameter number in the
 165    vector of parameters.  */
 166
 167 static inline int
 168 clast_name_to_level (clast_name_p name, htab_t index_table)
 169 {
 170   struct clast_name_index tmp;
 171   PTR *slot;
 172
 173   gcc_assert (name->type == clast_expr_name);
 174   tmp.name = ((const struct clast_name *) name)->name;
 175   tmp.free_name = NULL;
 176
 177   slot = htab_find_slot (index_table, &tmp, NO_INSERT);
 178
 179   if (slot && *slot)
 180     return ((struct clast_name_index *) *slot)->level;
 181
 182   return -1;
 183 }
 184
 185 /* For a given clast NAME, returns -1 if it does not correspond to any
 186    parameter, or otherwise, returns the index in the PARAMS or
 187    SCATTERING_DIMENSIONS vector.  */
 188
 189 static inline int
 190 clast_name_to_index (struct clast_name *name, htab_t index_table)
 191 {
 192   struct clast_name_index tmp;
 193   PTR *slot;
 194
 195   tmp.name = ((const struct clast_name *) name)->name;
 196   tmp.free_name = NULL;
 197
 198   slot = htab_find_slot (index_table, &tmp, NO_INSERT);
 199
 200   if (slot && *slot)
 201     return ((struct clast_name_index *) *slot)->index;
 202
 203   return -1;
 204 }
 205
 206 /* For a given clast NAME, initializes the lower and upper bounds BOUND_ONE
 207    and BOUND_TWO stored in the INDEX_TABLE.  Returns true when NAME has been
 208    found in the INDEX_TABLE, false otherwise.  */
 209
 210 static inline bool
 211 clast_name_to_lb_ub (struct clast_name *name, htab_t index_table,
 212                      mpz_t bound_one, mpz_t bound_two)
 213 {
 214   struct clast_name_index tmp;
 215   PTR *slot;
 216
 217   tmp.name = name->name;
 218   tmp.free_name = NULL;
 219
 220   slot = htab_find_slot (index_table, &tmp, NO_INSERT);
 221
 222   if (slot && *slot)
 223     {
 224       mpz_set (bound_one, ((struct clast_name_index *) *slot)->bound_one);
 225       mpz_set (bound_two, ((struct clast_name_index *) *slot)->bound_two);
 226       return true;
 227     }
 228
 229   return false;
 230 }
 231
 232 /* Records in INDEX_TABLE the INDEX and LEVEL for NAME.  */
 233
 234 static inline void
 235 save_clast_name_index (htab_t index_table, const char *name,
 236                        int index, int level, mpz_t bound_one, mpz_t bound_two)
 237 {
 238   struct clast_name_index tmp;
 239   PTR *slot;
 240
 241   tmp.name = name;
 242   tmp.free_name = NULL;
 243   slot = htab_find_slot (index_table, &tmp, INSERT);
 244
 245   if (slot)
 246     {
 247       free (*slot);
 248
 249       *slot = new_clast_name_index (name, index, level, bound_one, bound_two);
 250     }
 251 }
 252
 253 /* Computes a hash function for database element ELT.  */
 254
 255 static inline hashval_t
 256 clast_name_index_elt_info (const void *elt)
 257 {
 258   const struct clast_name_index *e = ((const struct clast_name_index *) elt);
 259   hashval_t hash = 0;
 260
 261   int length = strlen (e->name);
 262   int i;
 263
 264   for (i = 0; i < length; ++i)
 265     hash = hash | (e->name[i] << (i % 4));
 266
 267   return hash;
 268 }
 269
 270 /* Compares database elements E1 and E2.  */
 271
 272 static inline int
 273 eq_clast_name_indexes (const void *e1, const void *e2)
 274 {
 275   const struct clast_name_index *elt1 = (const struct clast_name_index *) e1;
 276   const struct clast_name_index *elt2 = (const struct clast_name_index *) e2;
 277
 278   return strcmp (elt1->name, elt2->name) == 0;
 279 }
 280
 281 \f
 282
 283 /* NEWIVS_INDEX binds CLooG's scattering name to the index of the tree
 284    induction variable in NEWIVS.
 285
 286    PARAMS_INDEX binds CLooG's parameter name to the index of the tree
 287    parameter in PARAMS.  */
 288
 289 typedef struct ivs_params {
 290   vec<tree> params, *newivs;
 291   htab_t newivs_index, params_index;
 292   sese region;
 293 } *ivs_params_p;
 294
 295 /* Returns the tree variable from the name NAME that was given in
 296    Cloog representation.  */
 297
 298 static tree
 299 clast_name_to_gcc (struct clast_name *name, ivs_params_p ip)
 300 {
 301   int index;
 302
 303   if (ip->params.exists () && ip->params_index)
 304     {
 305       index = clast_name_to_index (name, ip->params_index);
 306
 307       if (index >= 0)
 308         return ip->params[index];
 309     }
 310
 311   gcc_assert (ip->newivs && ip->newivs_index);
 312   index = clast_name_to_index (name, ip->newivs_index);
 313   gcc_assert (index >= 0);
 314
 315   return (*ip->newivs)[index];
 316 }
 317
 318 /* Returns the maximal precision type for expressions TYPE1 and TYPE2.  */
 319
 320 static tree
 321 max_precision_type (tree type1, tree type2)
 322 {
 323   enum machine_mode mode;
 324   int p1, p2, precision;
 325   tree type;
 326
 327   if (POINTER_TYPE_P (type1))
 328     return type1;
 329
 330   if (POINTER_TYPE_P (type2))
 331     return type2;
 332
 333   if (TYPE_UNSIGNED (type1)
 334       && TYPE_UNSIGNED (type2))
 335     return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
 336
 337   p1 = TYPE_PRECISION (type1);
 338   p2 = TYPE_PRECISION (type2);
 339
 340   if (p1 > p2)
 341     precision = TYPE_UNSIGNED (type1) ? p1 * 2 : p1;
 342   else
 343     precision = TYPE_UNSIGNED (type2) ? p2 * 2 : p2;
 344
 345   if (precision > BITS_PER_WORD)
 346     {
 347       gloog_error = true;
 348       return integer_type_node;
 349     }
 350
 351   mode = smallest_mode_for_size (precision, MODE_INT);
 352   precision = GET_MODE_PRECISION (mode);
 353   type = build_nonstandard_integer_type (precision, false);
 354
 355   if (!type)
 356     {
 357       gloog_error = true;
 358       return integer_type_node;
 359     }
 360
 361   return type;
 362 }
 363
 364 static tree
 365 clast_to_gcc_expression (tree, struct clast_expr *, ivs_params_p);
 366
 367 /* Converts a Cloog reduction expression R with reduction operation OP
 368    to a GCC expression tree of type TYPE.  */
 369
 370 static tree
 371 clast_to_gcc_expression_red (tree type, enum tree_code op,
 372                              struct clast_reduction *r, ivs_params_p ip)
 373 {
 374   int i;
 375   tree res = clast_to_gcc_expression (type, r->elts[0], ip);
 376   tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type;
 377
 378   for (i = 1; i < r->n; i++)
 379     {
 380       tree t = clast_to_gcc_expression (operand_type, r->elts[i], ip);
 381       res = fold_build2 (op, type, res, t);
 382     }
 383
 384   return res;
 385 }
 386
 387 /* Converts a Cloog AST expression E back to a GCC expression tree of
 388    type TYPE.  */
 389
 390 static tree
 391 clast_to_gcc_expression (tree type, struct clast_expr *e, ivs_params_p ip)
 392 {
 393   switch (e->type)
 394     {
 395     case clast_expr_name:
 396       {
 397         return clast_name_to_gcc ((struct clast_name *) e, ip);
 398       }
 399     case clast_expr_term:
 400       {
 401         struct clast_term *t = (struct clast_term *) e;
 402
 403         if (t->var)
 404           {
 405             if (mpz_cmp_si (t->val, 1) == 0)
 406               {
 407                 tree name = clast_to_gcc_expression (type, t->var, ip);
 408
 409                 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
 410                   name = convert_to_ptrofftype (name);
 411
 412                 name = fold_convert (type, name);
 413                 return name;
 414               }
 415
 416             else if (mpz_cmp_si (t->val, -1) == 0)
 417               {
 418                 tree name = clast_to_gcc_expression (type, t->var, ip);
 419
 420                 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
 421                   name = convert_to_ptrofftype (name);
 422
 423                 name = fold_convert (type, name);
 424
 425                 return fold_build1 (NEGATE_EXPR, type, name);
 426               }
 427             else
 428               {
 429                 tree name = clast_to_gcc_expression (type, t->var, ip);
 430                 tree cst = gmp_cst_to_tree (type, t->val);
 431
 432                 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
 433                   name = convert_to_ptrofftype (name);
 434
 435                 name = fold_convert (type, name);
 436
 437                 if (!POINTER_TYPE_P (type))
 438                   return fold_build2 (MULT_EXPR, type, cst, name);
 439
 440                 gloog_error = true;
 441                 return cst;
 442               }
 443           }
 444         else
 445           return gmp_cst_to_tree (type, t->val);
 446       }
 447
 448     case clast_expr_red:
 449       {
 450         struct clast_reduction *r = (struct clast_reduction *) e;
 451
 452         switch (r->type)
 453           {
 454           case clast_red_sum:
 455             return clast_to_gcc_expression_red
 456               (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
 457                r, ip);
 458
 459           case clast_red_min:
 460             return clast_to_gcc_expression_red (type, MIN_EXPR, r, ip);
 461
 462           case clast_red_max:
 463             return clast_to_gcc_expression_red (type, MAX_EXPR, r, ip);
 464
 465           default:
 466             gcc_unreachable ();
 467           }
 468         break;
 469       }
 470
 471     case clast_expr_bin:
 472       {
 473         struct clast_binary *b = (struct clast_binary *) e;
 474         struct clast_expr *lhs = (struct clast_expr *) b->LHS;
 475         tree tl = clast_to_gcc_expression (type, lhs, ip);
 476         tree tr = gmp_cst_to_tree (type, b->RHS);
 477
 478         switch (b->type)
 479           {
 480           case clast_bin_fdiv:
 481             return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
 482
 483           case clast_bin_cdiv:
 484             return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
 485
 486           case clast_bin_div:
 487             return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
 488
 489           case clast_bin_mod:
 490             return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
 491
 492           default:
 493             gcc_unreachable ();
 494           }
 495       }
 496
 497     default:
 498       gcc_unreachable ();
 499     }
 500
 501   return NULL_TREE;
 502 }
 503
 504 /* Return a type that could represent the values between BOUND_ONE and
 505    BOUND_TWO.  */
 506
 507 static tree
 508 type_for_interval (mpz_t bound_one, mpz_t bound_two)
 509 {
 510   bool unsigned_p;
 511   tree type;
 512   enum machine_mode mode;
 513   int wider_precision;
 514   int precision = MAX (mpz_sizeinbase (bound_one, 2),
 515                        mpz_sizeinbase (bound_two, 2));
 516
 517   if (precision > BITS_PER_WORD)
 518     {
 519       gloog_error = true;
 520       return integer_type_node;
 521     }
 522
 523   if (mpz_cmp (bound_one, bound_two) <= 0)
 524     unsigned_p = (mpz_sgn (bound_one) >= 0);
 525   else
 526     unsigned_p = (mpz_sgn (bound_two) >= 0);
 527
 528   mode = smallest_mode_for_size (precision, MODE_INT);
 529   wider_precision = GET_MODE_PRECISION (mode);
 530
 531   /* As we want to generate signed types as much as possible, try to
 532      fit the interval [bound_one, bound_two] in a signed type.  For example,
 533      supposing that we have the interval [0, 100], instead of
 534      generating unsigned char, we want to generate a signed char.  */
 535   if (unsigned_p && precision < wider_precision)
 536     unsigned_p = false;
 537
 538   type = build_nonstandard_integer_type (wider_precision, unsigned_p);
 539
 540   if (!type)
 541     {
 542       gloog_error = true;
 543       return integer_type_node;
 544     }
 545
 546   return type;
 547 }
 548
 549 /* Return a type that could represent the integer value VAL, or
 550    otherwise return NULL_TREE.  */
 551
 552 static tree
 553 type_for_value (mpz_t val)
 554 {
 555   return type_for_interval (val, val);
 556 }
 557
 558 static tree
 559 type_for_clast_expr (struct clast_expr *, ivs_params_p, mpz_t, mpz_t);
 560
 561 /* Return the type for the clast_term T.  Initializes BOUND_ONE and
 562    BOUND_TWO to the bounds of the term.  */
 563
 564 static tree
 565 type_for_clast_term (struct clast_term *t, ivs_params_p ip, mpz_t bound_one,
 566                      mpz_t bound_two)
 567 {
 568   tree type;
 569   gcc_assert (t->expr.type == clast_expr_term);
 570
 571   if (!t->var)
 572     {
 573       mpz_set (bound_one, t->val);
 574       mpz_set (bound_two, t->val);
 575       return type_for_value (t->val);
 576     }
 577
 578   type = type_for_clast_expr (t->var, ip, bound_one, bound_two);
 579
 580   mpz_mul (bound_one, bound_one, t->val);
 581   mpz_mul (bound_two, bound_two, t->val);
 582
 583   return max_precision_type (type, type_for_interval (bound_one, bound_two));
 584 }
 585
 586 /* Return the type for the clast_reduction R.  Initializes BOUND_ONE
 587    and BOUND_TWO to the bounds of the reduction expression.  */
 588
 589 static tree
 590 type_for_clast_red (struct clast_reduction *r, ivs_params_p ip,
 591                     mpz_t bound_one, mpz_t bound_two)
 592 {
 593   int i;
 594   tree type = type_for_clast_expr (r->elts[0], ip, bound_one, bound_two);
 595   mpz_t b1, b2, m1, m2;
 596
 597   if (r->n == 1)
 598     return type;
 599
 600   mpz_init (b1);
 601   mpz_init (b2);
 602   mpz_init (m1);
 603   mpz_init (m2);
 604
 605   for (i = 1; i < r->n; i++)
 606     {
 607       tree t = type_for_clast_expr (r->elts[i], ip, b1, b2);
 608       type = max_precision_type (type, t);
 609
 610       switch (r->type)
 611         {
 612         case clast_red_sum:
 613           value_min (m1, bound_one, bound_two);
 614           value_min (m2, b1, b2);
 615           mpz_add (bound_one, m1, m2);
 616
 617           value_max (m1, bound_one, bound_two);
 618           value_max (m2, b1, b2);
 619           mpz_add (bound_two, m1, m2);
 620           break;
 621
 622         case clast_red_min:
 623           value_min (bound_one, bound_one, bound_two);
 624           value_min (bound_two, b1, b2);
 625           break;
 626
 627         case clast_red_max:
 628           value_max (bound_one, bound_one, bound_two);
 629           value_max (bound_two, b1, b2);
 630           break;
 631
 632         default:
 633           gcc_unreachable ();
 634           break;
 635         }
 636     }
 637
 638   mpz_clear (b1);
 639   mpz_clear (b2);
 640   mpz_clear (m1);
 641   mpz_clear (m2);
 642
 643   /* Return a type that can represent the result of the reduction.  */
 644   return max_precision_type (type, type_for_interval (bound_one, bound_two));
 645 }
 646
 647 /* Return the type for the clast_binary B used in STMT.  */
 648
 649 static tree
 650 type_for_clast_bin (struct clast_binary *b, ivs_params_p ip, mpz_t bound_one,
 651                     mpz_t bound_two)
 652 {
 653   mpz_t one;
 654   tree l = type_for_clast_expr ((struct clast_expr *) b->LHS, ip,
 655                                 bound_one, bound_two);
 656   tree r = type_for_value (b->RHS);
 657   tree type = max_precision_type (l, r);
 658
 659   switch (b->type)
 660     {
 661     case clast_bin_fdiv:
 662       mpz_mdiv (bound_one, bound_one, b->RHS);
 663       mpz_mdiv (bound_two, bound_two, b->RHS);
 664       break;
 665
 666     case clast_bin_cdiv:
 667       mpz_mdiv (bound_one, bound_one, b->RHS);
 668       mpz_mdiv (bound_two, bound_two, b->RHS);
 669       mpz_init (one);
 670       mpz_add (bound_one, bound_one, one);
 671       mpz_add (bound_two, bound_two, one);
 672       mpz_clear (one);
 673       break;
 674
 675     case clast_bin_div:
 676       mpz_div (bound_one, bound_one, b->RHS);
 677       mpz_div (bound_two, bound_two, b->RHS);
 678       break;
 679
 680     case clast_bin_mod:
 681       mpz_mod (bound_one, bound_one, b->RHS);
 682       mpz_mod (bound_two, bound_two, b->RHS);
 683       break;
 684
 685     default:
 686       gcc_unreachable ();
 687     }
 688
 689   /* Return a type that can represent the result of the reduction.  */
 690   return max_precision_type (type, type_for_interval (bound_one, bound_two));
 691 }
 692
 693 /* Return the type for the clast_name NAME.  Initializes BOUND_ONE and
 694    BOUND_TWO to the bounds of the term.  */
 695
 696 static tree
 697 type_for_clast_name (struct clast_name *name, ivs_params_p ip, mpz_t bound_one,
 698                      mpz_t bound_two)
 699 {
 700   bool found = false;
 701
 702   if (ip->params.exists () && ip->params_index)
 703     found = clast_name_to_lb_ub (name, ip->params_index, bound_one, bound_two);
 704
 705   if (!found)
 706     {
 707       gcc_assert (ip->newivs && ip->newivs_index);
 708       found = clast_name_to_lb_ub (name, ip->newivs_index, bound_one,
 709                                    bound_two);
 710       gcc_assert (found);
 711     }
 712
 713     return TREE_TYPE (clast_name_to_gcc (name, ip));
 714 }
 715
 716 /* Returns the type for the CLAST expression E when used in statement
 717    STMT.  */
 718
 719 static tree
 720 type_for_clast_expr (struct clast_expr *e, ivs_params_p ip, mpz_t bound_one,
 721                      mpz_t bound_two)
 722 {
 723   switch (e->type)
 724     {
 725     case clast_expr_term:
 726       return type_for_clast_term ((struct clast_term *) e, ip,
 727                                   bound_one, bound_two);
 728
 729     case clast_expr_red:
 730       return type_for_clast_red ((struct clast_reduction *) e, ip,
 731                                  bound_one, bound_two);
 732
 733     case clast_expr_bin:
 734       return type_for_clast_bin ((struct clast_binary *) e, ip,
 735                                  bound_one, bound_two);
 736
 737     case clast_expr_name:
 738       return type_for_clast_name ((struct clast_name *) e, ip,
 739                                  bound_one, bound_two);
 740
 741     default:
 742       gcc_unreachable ();
 743     }
 744
 745   return NULL_TREE;
 746 }
 747
 748 /* Returns true if the clast expression E is a constant with VALUE.  */
 749
 750 static bool
 751 clast_expr_const_value_p (struct clast_expr *e, int value)
 752 {
 753   struct clast_term *t;
 754   if (e->type != clast_expr_term)
 755     return false;
 756   t = (struct clast_term *)e;
 757   if (t->var)
 758     return false;
 759   return 0 == mpz_cmp_si (t->val, value);
 760 }
 761
 762 /* Translates a clast equation CLEQ to a tree.  */
 763
 764 static tree
 765 graphite_translate_clast_equation (struct clast_equation *cleq,
 766                                    ivs_params_p ip)
 767 {
 768   enum tree_code comp;
 769   tree type, lhs, rhs, ltype, rtype;
 770   mpz_t bound_one, bound_two;
 771   struct clast_expr *clhs, *crhs;
 772
 773   clhs = cleq->LHS;
 774   crhs = cleq->RHS;
 775   if (cleq->sign == 0)
 776     comp = EQ_EXPR;
 777   else if (cleq->sign > 0)
 778     comp = GE_EXPR;
 779   else
 780     comp = LE_EXPR;
 781
 782   /* Special cases to reduce range of arguments to hopefully
 783      don't need types with larger precision than the input.  */
 784   if (crhs->type == clast_expr_red
 785       && comp != EQ_EXPR)
 786     {
 787       struct clast_reduction *r = (struct clast_reduction *) crhs;
 788       /* X >= A+1 --> X > A and
 789          X <= A-1 --> X < A  */
 790       if (r->n == 2
 791           && r->type == clast_red_sum
 792           && clast_expr_const_value_p (r->elts[1], comp == GE_EXPR ? 1 : -1))
 793         {
 794           crhs = r->elts[0];
 795           comp = comp == GE_EXPR ? GT_EXPR : LT_EXPR;
 796         }
 797     }
 798
 799   mpz_init (bound_one);
 800   mpz_init (bound_two);
 801
 802   ltype = type_for_clast_expr (clhs, ip, bound_one, bound_two);
 803   rtype = type_for_clast_expr (crhs, ip, bound_one, bound_two);
 804
 805   mpz_clear (bound_one);
 806   mpz_clear (bound_two);
 807   type = max_precision_type (ltype, rtype);
 808
 809   lhs = clast_to_gcc_expression (type, clhs, ip);
 810   rhs = clast_to_gcc_expression (type, crhs, ip);
 811
 812   return fold_build2 (comp, boolean_type_node, lhs, rhs);
 813 }
 814
 815 /* Creates the test for the condition in STMT.  */
 816
 817 static tree
 818 graphite_create_guard_cond_expr (struct clast_guard *stmt,
 819                                  ivs_params_p ip)
 820 {
 821   tree cond = NULL;
 822   int i;
 823
 824   for (i = 0; i < stmt->n; i++)
 825     {
 826       tree eq = graphite_translate_clast_equation (&stmt->eq[i], ip);
 827
 828       if (cond)
 829         cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
 830       else
 831         cond = eq;
 832     }
 833
 834   return cond;
 835 }
 836
 837 /* Creates a new if region corresponding to Cloog's guard.  */
 838
 839 static edge
 840 graphite_create_new_guard (edge entry_edge, struct clast_guard *stmt,
 841                            ivs_params_p ip)
 842 {
 843   tree cond_expr = graphite_create_guard_cond_expr (stmt, ip);
 844   edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
 845   return exit_edge;
 846 }
 847
 848 /* Compute the lower bound LOW and upper bound UP for the parameter
 849    PARAM in scop SCOP based on the constraints in the context.  */
 850
 851 static void
 852 compute_bounds_for_param (scop_p scop, int param, mpz_t low, mpz_t up)
 853 {
 854   isl_int v;
 855   isl_aff *aff = isl_aff_zero_on_domain
 856     (isl_local_space_from_space (isl_set_get_space (scop->context)));
 857
 858   aff = isl_aff_add_coefficient_si (aff, isl_dim_param, param, 1);
 859
 860   isl_int_init (v);
 861   isl_set_min (scop->context, aff, &v);
 862   isl_int_get_gmp (v, low);
 863   isl_set_max (scop->context, aff, &v);
 864   isl_int_get_gmp (v, up);
 865   isl_int_clear (v);
 866   isl_aff_free (aff);
 867 }
 868
 869 /* Compute the lower bound LOW and upper bound UP for the induction
 870    variable of loop LOOP.
 871
 872    FIXME: This one is not entirely correct, as min/max expressions in the
 873           calculation can yield to incorrect results. To be completely
 874           correct, we need to evaluate each subexpression generated by
 875           CLooG. CLooG does not yet support this, so this is as good as
 876           it can be. */
 877
 878 static void
 879 compute_bounds_for_loop (struct clast_for *loop, mpz_t low, mpz_t up)
 880 {
 881   isl_set *domain;
 882   isl_aff *dimension;
 883   isl_local_space *local_space;
 884   isl_int isl_value;
 885   enum isl_lp_result lp_result;
 886
 887   domain = isl_set_copy (isl_set_from_cloog_domain (loop->domain));
 888   local_space = isl_local_space_from_space (isl_set_get_space (domain));
 889   dimension = isl_aff_zero_on_domain (local_space);
 890   dimension = isl_aff_add_coefficient_si (dimension, isl_dim_in,
 891                                           isl_set_dim (domain, isl_dim_set) - 1,
 892                                           1);
 893
 894   isl_int_init (isl_value);
 895
 896   lp_result = isl_set_min (domain, dimension, &isl_value);
 897   assert (lp_result == isl_lp_ok);
 898   isl_int_get_gmp (isl_value, low);
 899
 900   lp_result = isl_set_max (domain, dimension, &isl_value);
 901   assert (lp_result == isl_lp_ok);
 902   isl_int_get_gmp (isl_value, up);
 903
 904   isl_int_clear (isl_value);
 905   isl_set_free (domain);
 906   isl_aff_free (dimension);
 907 }
 908
 909 /* Returns the type for the induction variable for the loop translated
 910    from STMT_FOR.  */
 911
 912 static tree
 913 type_for_clast_for (struct clast_for *stmt_for, ivs_params_p ip)
 914 {
 915   mpz_t bound_one, bound_two;
 916   tree lb_type, ub_type;
 917
 918   mpz_init (bound_one);
 919   mpz_init (bound_two);
 920
 921   lb_type = type_for_clast_expr (stmt_for->LB, ip, bound_one, bound_two);
 922   ub_type = type_for_clast_expr (stmt_for->UB, ip, bound_one, bound_two);
 923
 924   mpz_clear (bound_one);
 925   mpz_clear (bound_two);
 926
 927   return max_precision_type (lb_type, ub_type);
 928 }
 929
 930 /* Creates a new LOOP corresponding to Cloog's STMT.  Inserts an
 931    induction variable for the new LOOP.  New LOOP is attached to CFG
 932    starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
 933    becomes the child loop of the OUTER_LOOP.  NEWIVS_INDEX binds
 934    CLooG's scattering name to the induction variable created for the
 935    loop of STMT.  The new induction variable is inserted in the NEWIVS
 936    vector and is of type TYPE.  */
 937
 938 static struct loop *
 939 graphite_create_new_loop (edge entry_edge, struct clast_for *stmt,
 940                           loop_p outer, tree type, tree lb, tree ub,
 941                           int level, ivs_params_p ip)
 942 {
 943   mpz_t low, up;
 944
 945   tree stride = gmp_cst_to_tree (type, stmt->stride);
 946   tree ivvar = create_tmp_var (type, "graphite_IV");
 947   tree iv, iv_after_increment;
 948   loop_p loop = create_empty_loop_on_edge
 949     (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
 950      outer ? outer : entry_edge->src->loop_father);
 951
 952   mpz_init (low);
 953   mpz_init (up);
 954   compute_bounds_for_loop (stmt, low, up);
 955   save_clast_name_index (ip->newivs_index, stmt->iterator,
 956                          (*ip->newivs).length (), level, low, up);
 957   mpz_clear (low);
 958   mpz_clear (up);
 959   (*ip->newivs).safe_push (iv);
 960   return loop;
 961 }
 962
 963 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the
 964    induction variables of the loops around GBB in SESE.  */
 965
 966 static void
 967 build_iv_mapping (vec<tree> iv_map, struct clast_user_stmt *user_stmt,
 968                   ivs_params_p ip)
 969 {
 970   struct clast_stmt *t;
 971   int depth = 0;
 972   CloogStatement *cs = user_stmt->statement;
 973   poly_bb_p pbb = (poly_bb_p) cs->usr;
 974   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
 975   mpz_t bound_one, bound_two;
 976
 977   mpz_init (bound_one);
 978   mpz_init (bound_two);
 979
 980   for (t = user_stmt->substitutions; t; t = t->next, depth++)
 981     {
 982       struct clast_expr *expr = (struct clast_expr *)
 983        ((struct clast_assignment *)t)->RHS;
 984       tree type = type_for_clast_expr (expr, ip, bound_one, bound_two);
 985       tree new_name = clast_to_gcc_expression (type, expr, ip);
 986       loop_p old_loop = gbb_loop_at_index (gbb, ip->region, depth);
 987
 988       iv_map[old_loop->num] = new_name;
 989     }
 990
 991   mpz_clear (bound_one);
 992   mpz_clear (bound_two);
 993 }
 994
 995 /* Construct bb_pbb_def with BB and PBB.  */
 996
 997 static bb_pbb_def *
 998 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
 999 {
1000   bb_pbb_def *bb_pbb_p;
1001
1002   bb_pbb_p = XNEW (bb_pbb_def);
1003   bb_pbb_p->bb = bb;
1004   bb_pbb_p->pbb = pbb;
1005
1006   return bb_pbb_p;
1007 }
1008
1009 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING.  */
1010
1011 static void
1012 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
1013 {
1014   bb_pbb_def tmp;
1015   PTR *x;
1016
1017   tmp.bb = bb;
1018   x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
1019
1020   if (x && !*x)
1021     *x = new_bb_pbb_def (bb, pbb);
1022 }
1023
1024 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING.  */
1025
1026 poly_bb_p
1027 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
1028 {
1029   bb_pbb_def tmp;
1030   PTR *slot;
1031
1032   tmp.bb = bb;
1033   slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
1034
1035   if (slot && *slot)
1036     return ((bb_pbb_def *) *slot)->pbb;
1037
1038   return NULL;
1039 }
1040
1041 /* Return the scop of the loop and initialize PBBS the set of
1042    poly_bb_p that belong to the LOOP.  BB_PBB_MAPPING is a map created
1043    by the CLAST code generator between a generated basic_block and its
1044    related poly_bb_p.  */
1045
1046 scop_p
1047 get_loop_body_pbbs (loop_p loop, htab_t bb_pbb_mapping,
1048                     vec<poly_bb_p> *pbbs)
1049 {
1050   unsigned i;
1051   basic_block *bbs = get_loop_body_in_dom_order (loop);
1052   scop_p scop = NULL;
1053
1054   for (i = 0; i < loop->num_nodes; i++)
1055     {
1056       poly_bb_p pbb = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
1057
1058       if (pbb == NULL)
1059         continue;
1060
1061       scop = PBB_SCOP (pbb);
1062       (*pbbs).safe_push (pbb);
1063     }
1064
1065   free (bbs);
1066   return scop;
1067 }
1068
1069 /* Translates a clast user statement STMT to gimple.
1070
1071    - NEXT_E is the edge where new generated code should be attached.
1072    - CONTEXT_LOOP is the loop in which the generated code will be placed
1073    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
1074
1075 static edge
1076 translate_clast_user (struct clast_user_stmt *stmt, edge next_e,
1077                       htab_t bb_pbb_mapping, ivs_params_p ip)
1078 {
1079   int i, nb_loops;
1080   basic_block new_bb;
1081   poly_bb_p pbb = (poly_bb_p) stmt->statement->usr;
1082   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1083   vec<tree> iv_map;
1084
1085   if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
1086     return next_e;
1087
1088   nb_loops = number_of_loops ();
1089   iv_map.create (nb_loops);
1090   for (i = 0; i < nb_loops; i++)
1091     iv_map.quick_push (NULL_TREE);
1092
1093   build_iv_mapping (iv_map, stmt, ip);
1094   next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), ip->region,
1095                                            next_e, iv_map, &gloog_error);
1096   iv_map.release ();
1097
1098   new_bb = next_e->src;
1099   mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
1100   mark_virtual_operands_for_renaming (cfun);
1101   update_ssa (TODO_update_ssa);
1102
1103   return next_e;
1104 }
1105
1106 /* Creates a new if region protecting the loop to be executed, if the execution
1107    count is zero (lb > ub).  */
1108
1109 static edge
1110 graphite_create_new_loop_guard (edge entry_edge, struct clast_for *stmt,
1111                                 tree *type, tree *lb, tree *ub,
1112                                 ivs_params_p ip)
1113 {
1114   tree cond_expr;
1115   edge exit_edge;
1116
1117   *type = type_for_clast_for (stmt, ip);
1118   *lb = clast_to_gcc_expression (*type, stmt->LB, ip);
1119   *ub = clast_to_gcc_expression (*type, stmt->UB, ip);
1120
1121   /* When ub is simply a constant or a parameter, use lb <= ub.  */
1122   if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
1123     cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
1124   else
1125     {
1126       tree one = (POINTER_TYPE_P (*type)
1127                   ? convert_to_ptrofftype (integer_one_node)
1128                   : fold_convert (*type, integer_one_node));
1129       /* Adding +1 and using LT_EXPR helps with loop latches that have a
1130          loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this becomes
1131          2^k-1 due to integer overflow, and the condition lb <= ub is true,
1132          even if we do not want this.  However lb < ub + 1 is false, as
1133          expected.  */
1134       tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
1135                                  : PLUS_EXPR, *type, *ub, one);
1136
1137       cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
1138     }
1139
1140   exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
1141
1142   return exit_edge;
1143 }
1144
1145 static edge
1146 translate_clast (loop_p, struct clast_stmt *, edge, htab_t, int, ivs_params_p);
1147
1148 /* Create the loop for a clast for statement.
1149
1150    - NEXT_E is the edge where new generated code should be attached.
1151    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
1152
1153 static edge
1154 translate_clast_for_loop (loop_p context_loop, struct clast_for *stmt,
1155                           edge next_e, htab_t bb_pbb_mapping, int level,
1156                           tree type, tree lb, tree ub, ivs_params_p ip)
1157 {
1158   struct loop *loop = graphite_create_new_loop (next_e, stmt, context_loop,
1159                                                 type, lb, ub, level, ip);
1160   edge last_e = single_exit (loop);
1161   edge to_body = single_succ_edge (loop->header);
1162   basic_block after = to_body->dest;
1163
1164   /* Create a basic block for loop close phi nodes.  */
1165   last_e = single_succ_edge (split_edge (last_e));
1166
1167   /* Translate the body of the loop.  */
1168   next_e = translate_clast (loop, stmt->body, to_body, bb_pbb_mapping,
1169                             level + 1, ip);
1170   redirect_edge_succ_nodup (next_e, after);
1171   set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
1172
1173   if (flag_loop_parallelize_all
1174       && loop_is_parallel_p (loop, bb_pbb_mapping, level))
1175     loop->can_be_parallel = true;
1176
1177   return last_e;
1178 }
1179
1180 /* Translates a clast for statement STMT to gimple.  First a guard is created
1181    protecting the loop, if it is executed zero times.  In this guard we create
1182    the real loop structure.
1183
1184    - NEXT_E is the edge where new generated code should be attached.
1185    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
1186
1187 static edge
1188 translate_clast_for (loop_p context_loop, struct clast_for *stmt, edge next_e,
1189                      htab_t bb_pbb_mapping, int level, ivs_params_p ip)
1190 {
1191   tree type, lb, ub;
1192   edge last_e = graphite_create_new_loop_guard (next_e, stmt, &type,
1193                                                 &lb, &ub, ip);
1194   edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1195
1196   translate_clast_for_loop (context_loop, stmt, true_e, bb_pbb_mapping, level,
1197                             type, lb, ub, ip);
1198   return last_e;
1199 }
1200
1201 /* Translates a clast assignment STMT to gimple.
1202
1203    - NEXT_E is the edge where new generated code should be attached.
1204    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
1205
1206 static edge
1207 translate_clast_assignment (struct clast_assignment *stmt, edge next_e,
1208                             int level, ivs_params_p ip)
1209 {
1210   gimple_seq stmts;
1211   mpz_t bound_one, bound_two;
1212   tree type, new_name, var;
1213   edge res = single_succ_edge (split_edge (next_e));
1214   struct clast_expr *expr = (struct clast_expr *) stmt->RHS;
1215
1216   mpz_init (bound_one);
1217   mpz_init (bound_two);
1218   type = type_for_clast_expr (expr, ip, bound_one, bound_two);
1219   var = create_tmp_var (type, "graphite_var");
1220   new_name = force_gimple_operand (clast_to_gcc_expression (type, expr, ip),
1221                                    &stmts, true, var);
1222   if (stmts)
1223     {
1224       gsi_insert_seq_on_edge (next_e, stmts);
1225       gsi_commit_edge_inserts ();
1226     }
1227
1228   save_clast_name_index (ip->newivs_index, stmt->LHS,
1229                          (*ip->newivs).length (), level,
1230                          bound_one, bound_two);
1231   (*ip->newivs).safe_push (new_name);
1232
1233   mpz_clear (bound_one);
1234   mpz_clear (bound_two);
1235
1236   return res;
1237 }
1238
1239 /* Translates a clast guard statement STMT to gimple.
1240
1241    - NEXT_E is the edge where new generated code should be attached.
1242    - CONTEXT_LOOP is the loop in which the generated code will be placed
1243    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
1244
1245 static edge
1246 translate_clast_guard (loop_p context_loop, struct clast_guard *stmt,
1247                        edge next_e, htab_t bb_pbb_mapping, int level,
1248                        ivs_params_p ip)
1249 {
1250   edge last_e = graphite_create_new_guard (next_e, stmt, ip);
1251   edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1252
1253   translate_clast (context_loop, stmt->then, true_e, bb_pbb_mapping, level, ip);
1254   return last_e;
1255 }
1256
1257 /* Translates a CLAST statement STMT to GCC representation in the
1258    context of a SESE.
1259
1260    - NEXT_E is the edge where new generated code should be attached.
1261    - CONTEXT_LOOP is the loop in which the generated code will be placed
1262    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
1263
1264 static edge
1265 translate_clast (loop_p context_loop, struct clast_stmt *stmt, edge next_e,
1266                  htab_t bb_pbb_mapping, int level, ivs_params_p ip)
1267 {
1268   if (!stmt)
1269     return next_e;
1270
1271   if (CLAST_STMT_IS_A (stmt, stmt_root))
1272     ; /* Do nothing.  */
1273
1274   else if (CLAST_STMT_IS_A (stmt, stmt_user))
1275     next_e = translate_clast_user ((struct clast_user_stmt *) stmt,
1276                                    next_e, bb_pbb_mapping, ip);
1277
1278   else if (CLAST_STMT_IS_A (stmt, stmt_for))
1279     next_e = translate_clast_for (context_loop, (struct clast_for *) stmt,
1280                                   next_e, bb_pbb_mapping, level, ip);
1281
1282   else if (CLAST_STMT_IS_A (stmt, stmt_guard))
1283     next_e = translate_clast_guard (context_loop, (struct clast_guard *) stmt,
1284                                     next_e, bb_pbb_mapping, level, ip);
1285
1286   else if (CLAST_STMT_IS_A (stmt, stmt_block))
1287     next_e = translate_clast (context_loop, ((struct clast_block *) stmt)->body,
1288                               next_e, bb_pbb_mapping, level, ip);
1289
1290   else if (CLAST_STMT_IS_A (stmt, stmt_ass))
1291     next_e = translate_clast_assignment ((struct clast_assignment *) stmt,
1292                                          next_e, level, ip);
1293   else
1294     gcc_unreachable();
1295
1296   recompute_all_dominators ();
1297   graphite_verify ();
1298
1299   return translate_clast (context_loop, stmt->next, next_e, bb_pbb_mapping,
1300                           level, ip);
1301 }
1302
1303 /* Add parameter and iterator names to the CloogUnionDomain.  */
1304
1305 static CloogUnionDomain *
1306 add_names_to_union_domain (scop_p scop, CloogUnionDomain *union_domain,
1307                            int nb_scattering_dims, htab_t params_index)
1308 {
1309   sese region = SCOP_REGION (scop);
1310   int i;
1311   int nb_iterators = scop_max_loop_depth (scop);
1312   int nb_parameters = SESE_PARAMS (region).length ();
1313   mpz_t bound_one, bound_two;
1314
1315   mpz_init (bound_one);
1316   mpz_init (bound_two);
1317
1318   for (i = 0; i < nb_parameters; i++)
1319     {
1320       tree param = SESE_PARAMS (region)[i];
1321       const char *name = get_name (param);
1322       int len;
1323       char *parameter;
1324
1325       if (!name)
1326         name = "T";
1327
1328       len = strlen (name);
1329       len += 17;
1330       parameter = XNEWVEC (char, len + 1);
1331       snprintf (parameter, len, "%s_%d", name, SSA_NAME_VERSION (param));
1332       save_clast_name_index (params_index, parameter, i, i, bound_one,
1333                              bound_two);
1334       union_domain = cloog_union_domain_set_name (union_domain, CLOOG_PARAM, i,
1335                                                   parameter);
1336       compute_bounds_for_param (scop, i, bound_one, bound_two);
1337       free (parameter);
1338     }
1339
1340   mpz_clear (bound_one);
1341   mpz_clear (bound_two);
1342
1343   for (i = 0; i < nb_iterators; i++)
1344     {
1345       int len = 4 + 16;
1346       char *iterator;
1347       iterator = XNEWVEC (char, len);
1348       snprintf (iterator, len, "git_%d", i);
1349       union_domain = cloog_union_domain_set_name (union_domain, CLOOG_ITER, i,
1350                                                   iterator);
1351       free (iterator);
1352     }
1353
1354   for (i = 0; i < nb_scattering_dims; i++)
1355     {
1356       int len = 5 + 16;
1357       char *scattering;
1358       scattering = XNEWVEC (char, len);
1359       snprintf (scattering, len, "scat_%d", i);
1360       union_domain = cloog_union_domain_set_name (union_domain, CLOOG_SCAT, i,
1361                                                   scattering);
1362       free (scattering);
1363     }
1364
1365   return union_domain;
1366 }
1367
1368 /* Initialize a CLooG input file.  */
1369
1370 static FILE *
1371 init_cloog_input_file (int scop_number)
1372 {
1373   FILE *graphite_out_file;
1374   int len = strlen (dump_base_name);
1375   char *dumpname = XNEWVEC (char, len + 25);
1376   char *s_scop_number = XNEWVEC (char, 15);
1377
1378   memcpy (dumpname, dump_base_name, len + 1);
1379   strip_off_ending (dumpname, len);
1380   sprintf (s_scop_number, ".%d", scop_number);
1381   strcat (dumpname, s_scop_number);
1382   strcat (dumpname, ".cloog");
1383   graphite_out_file = fopen (dumpname, "w+b");
1384
1385   if (graphite_out_file == 0)
1386     fatal_error ("can%'t open %s for writing: %m", dumpname);
1387
1388   free (dumpname);
1389
1390   return graphite_out_file;
1391 }
1392
1393 /* Extend the scattering to NEW_DIMS scattering dimensions.  */
1394
1395 static
1396 isl_map *extend_scattering(isl_map *scattering, int new_dims)
1397 {
1398   int old_dims, i;
1399   isl_space *space;
1400   isl_basic_map *change_scattering;
1401   isl_map *change_scattering_map;
1402
1403   old_dims = isl_map_dim (scattering, isl_dim_out);
1404
1405   space = isl_space_alloc (isl_map_get_ctx (scattering), 0, old_dims, new_dims);
1406   change_scattering = isl_basic_map_universe (isl_space_copy (space));
1407
1408   for (i = 0; i < old_dims; i++)
1409     {
1410       isl_constraint *c;
1411       c = isl_equality_alloc
1412         (isl_local_space_from_space (isl_space_copy (space)));
1413       isl_constraint_set_coefficient_si (c, isl_dim_in, i, 1);
1414       isl_constraint_set_coefficient_si (c, isl_dim_out, i, -1);
1415       change_scattering = isl_basic_map_add_constraint (change_scattering, c);
1416     }
1417
1418   for (i = old_dims; i < new_dims; i++)
1419     {
1420       isl_constraint *c;
1421       c = isl_equality_alloc
1422         (isl_local_space_from_space (isl_space_copy (space)));
1423       isl_constraint_set_coefficient_si (c, isl_dim_out, i, 1);
1424       change_scattering = isl_basic_map_add_constraint (change_scattering, c);
1425     }
1426
1427   change_scattering_map = isl_map_from_basic_map (change_scattering);
1428   change_scattering_map = isl_map_align_params (change_scattering_map, space);
1429   return isl_map_apply_range (scattering, change_scattering_map);
1430 }
1431
1432 /* Build cloog union domain for SCoP.  */
1433
1434 static CloogUnionDomain *
1435 build_cloog_union_domain (scop_p scop, int nb_scattering_dims)
1436 {
1437   int i;
1438   poly_bb_p pbb;
1439   CloogUnionDomain *union_domain =
1440     cloog_union_domain_alloc (scop_nb_params (scop));
1441
1442   FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
1443     {
1444       CloogDomain *domain;
1445       CloogScattering *scattering;
1446
1447       /* Dead code elimination: when the domain of a PBB is empty,
1448          don't generate code for the PBB.  */
1449       if (isl_set_is_empty(pbb->domain))
1450         continue;
1451
1452       domain = cloog_domain_from_isl_set(isl_set_copy(pbb->domain));
1453       scattering = cloog_scattering_from_isl_map(extend_scattering(isl_map_copy(pbb->transformed),
1454                                                  nb_scattering_dims));
1455
1456       union_domain = cloog_union_domain_add_domain (union_domain, "", domain,
1457                                                     scattering, pbb);
1458     }
1459
1460   return union_domain;
1461 }
1462
1463 /* Return the options that will be used in GLOOG.  */
1464
1465 static CloogOptions *
1466 set_cloog_options (void)
1467 {
1468   CloogOptions *options = cloog_options_malloc (cloog_state);
1469
1470   /* Change cloog output language to C.  If we do use FORTRAN instead, cloog
1471      will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1472      we pass an incomplete program to cloog.  */
1473   options->language = CLOOG_LANGUAGE_C;
1474
1475   /* Enable complex equality spreading: removes dummy statements
1476      (assignments) in the generated code which repeats the
1477      substitution equations for statements.  This is useless for
1478      GLooG.  */
1479   options->esp = 1;
1480
1481   /* Silence CLooG to avoid failing tests due to debug output to stderr.  */
1482   options->quiet = 1;
1483
1484   /* Allow cloog to build strides with a stride width different to one.
1485      This example has stride = 4:
1486
1487      for (i = 0; i < 20; i += 4)
1488        A  */
1489   options->strides = 1;
1490
1491   /* We want the clast to provide the iteration domains of the executed loops.
1492      This allows us to derive minimal/maximal values for the induction
1493      variables.  */
1494   options->save_domains = 1;
1495
1496   /* Disable optimizations and make cloog generate source code closer to the
1497      input.  This is useful for debugging,  but later we want the optimized
1498      code.
1499
1500      XXX: We can not disable optimizations, as loop blocking is not working
1501      without them.  */
1502   if (0)
1503     {
1504       options->f = -1;
1505       options->l = INT_MAX;
1506     }
1507
1508   return options;
1509 }
1510
1511 /* Prints STMT to STDERR.  */
1512
1513 void
1514 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1515 {
1516   CloogOptions *options = set_cloog_options ();
1517
1518   clast_pprint (file, stmt, 0, options);
1519   cloog_options_free (options);
1520 }
1521
1522 /* Prints STMT to STDERR.  */
1523
1524 DEBUG_FUNCTION void
1525 debug_clast_stmt (struct clast_stmt *stmt)
1526 {
1527   print_clast_stmt (stderr, stmt);
1528 }
1529
1530 /* Get the maximal number of scattering dimensions in the scop SCOP.  */
1531
1532 static
1533 int get_max_scattering_dimensions (scop_p scop)
1534 {
1535   int i;
1536   poly_bb_p pbb;
1537   int scattering_dims = 0;
1538
1539   FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
1540     {
1541       int pbb_scatt_dims = isl_map_dim (pbb->transformed, isl_dim_out);
1542       if (pbb_scatt_dims > scattering_dims)
1543         scattering_dims = pbb_scatt_dims;
1544     }
1545
1546   return scattering_dims;
1547 }
1548
1549 static CloogInput *
1550 generate_cloog_input (scop_p scop, htab_t params_index)
1551 {
1552   CloogUnionDomain *union_domain;
1553   CloogInput *cloog_input;
1554   CloogDomain *context;
1555   int nb_scattering_dims = get_max_scattering_dimensions (scop);
1556
1557   union_domain = build_cloog_union_domain (scop, nb_scattering_dims);
1558   union_domain = add_names_to_union_domain (scop, union_domain,
1559                                             nb_scattering_dims,
1560                                             params_index);
1561   context = cloog_domain_from_isl_set (isl_set_copy (scop->context));
1562
1563   cloog_input = cloog_input_alloc (context, union_domain);
1564
1565   return cloog_input;
1566 }
1567
1568 /* Translate SCOP to a CLooG program and clast.  These two
1569    representations should be freed together: a clast cannot be used
1570    without a program.  */
1571
1572 static struct clast_stmt *
1573 scop_to_clast (scop_p scop, htab_t params_index)
1574 {
1575   CloogInput *cloog_input;
1576   struct clast_stmt *clast;
1577   CloogOptions *options = set_cloog_options ();
1578
1579   cloog_input = generate_cloog_input (scop, params_index);
1580
1581   /* Dump a .cloog input file, if requested.  This feature is only
1582      enabled in the Graphite branch.  */
1583   if (0)
1584   {
1585     static size_t file_scop_number = 0;
1586     FILE *cloog_file = init_cloog_input_file (file_scop_number);
1587     cloog_input_dump_cloog (cloog_file, cloog_input, options);
1588   }
1589
1590   clast = cloog_clast_create_from_input (cloog_input, options);
1591
1592   cloog_options_free (options);
1593   return clast;
1594 }
1595
1596 /* Prints to FILE the code generated by CLooG for SCOP.  */
1597
1598 void
1599 print_generated_program (FILE *file, scop_p scop)
1600 {
1601   CloogOptions *options = set_cloog_options ();
1602   htab_t params_index;
1603   struct clast_stmt *clast;
1604
1605   params_index = htab_create (10, clast_name_index_elt_info,
1606             eq_clast_name_indexes, free_clast_name_index);
1607
1608   clast = scop_to_clast (scop, params_index);
1609
1610   fprintf (file, "       (clast: \n");
1611   clast_pprint (file, clast, 0, options);
1612   fprintf (file, "       )\n");
1613
1614   cloog_options_free (options);
1615   cloog_clast_free (clast);
1616 }
1617
1618 /* Prints to STDERR the code generated by CLooG for SCOP.  */
1619
1620 DEBUG_FUNCTION void
1621 debug_generated_program (scop_p scop)
1622 {
1623   print_generated_program (stderr, scop);
1624 }
1625
1626 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1627    the given SCOP.  Return true if code generation succeeded.
1628    BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1629 */
1630
1631 bool
1632 gloog (scop_p scop, htab_t bb_pbb_mapping)
1633 {
1634   vec<tree> newivs;
1635   newivs.create (10);
1636   loop_p context_loop;
1637   sese region = SCOP_REGION (scop);
1638   ifsese if_region = NULL;
1639   htab_t newivs_index, params_index;
1640   struct clast_stmt *clast;
1641   struct ivs_params ip;
1642
1643   timevar_push (TV_GRAPHITE_CODE_GEN);
1644   gloog_error = false;
1645
1646   params_index = htab_create (10, clast_name_index_elt_info,
1647                               eq_clast_name_indexes, free_clast_name_index);
1648
1649   clast = scop_to_clast (scop, params_index);
1650
1651   if (dump_file && (dump_flags & TDF_DETAILS))
1652     {
1653       fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1654       print_clast_stmt (dump_file, clast);
1655       fprintf (dump_file, "\n");
1656     }
1657
1658   recompute_all_dominators ();
1659   graphite_verify ();
1660
1661   if_region = move_sese_in_condition (region);
1662   sese_insert_phis_for_liveouts (region,
1663                                  if_region->region->exit->src,
1664                                  if_region->false_region->exit,
1665                                  if_region->true_region->exit);
1666   recompute_all_dominators ();
1667   graphite_verify ();
1668
1669   context_loop = SESE_ENTRY (region)->src->loop_father;
1670   newivs_index = htab_create (10, clast_name_index_elt_info,
1671                               eq_clast_name_indexes, free_clast_name_index);
1672
1673   ip.newivs = &newivs;
1674   ip.newivs_index = newivs_index;
1675   ip.params = SESE_PARAMS (region);
1676   ip.params_index = params_index;
1677   ip.region = region;
1678
1679   translate_clast (context_loop, clast, if_region->true_region->entry,
1680                    bb_pbb_mapping, 0, &ip);
1681   graphite_verify ();
1682   scev_reset ();
1683   recompute_all_dominators ();
1684   graphite_verify ();
1685
1686   if (gloog_error)
1687     set_ifsese_condition (if_region, integer_zero_node);
1688
1689   free (if_region->true_region);
1690   free (if_region->region);
1691   free (if_region);
1692
1693   htab_delete (newivs_index);
1694   htab_delete (params_index);
1695   newivs.release ();
1696   cloog_clast_free (clast);
1697   timevar_pop (TV_GRAPHITE_CODE_GEN);
1698
1699   if (dump_file && (dump_flags & TDF_DETAILS))
1700     {
1701       loop_p loop;
1702       loop_iterator li;
1703       int num_no_dependency = 0;
1704
1705       FOR_EACH_LOOP (li, loop, 0)
1706         if (loop->can_be_parallel)
1707           num_no_dependency++;
1708
1709       fprintf (dump_file, "\n%d loops carried no dependency.\n",
1710                num_no_dependency);
1711     }
1712
1713   return !gloog_error;
1714 }
1715 #endif