gcc/graphite-clast-to-gimple.c

   1 /* Translation of CLAST (CLooG AST) to Gimple.
   2    Copyright (C) 2009 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 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "ggc.h"
  26 #include "tree.h"
  27 #include "rtl.h"
  28 #include "basic-block.h"
  29 #include "diagnostic.h"
  30 #include "tree-flow.h"
  31 #include "toplev.h"
  32 #include "tree-dump.h"
  33 #include "timevar.h"
  34 #include "cfgloop.h"
  35 #include "tree-chrec.h"
  36 #include "tree-data-ref.h"
  37 #include "tree-scalar-evolution.h"
  38 #include "tree-pass.h"
  39 #include "domwalk.h"
  40 #include "value-prof.h"
  41 #include "pointer-set.h"
  42 #include "gimple.h"
  43 #include "sese.h"
  44
  45 #ifdef HAVE_cloog
  46 #include "cloog/cloog.h"
  47 #include "ppl_c.h"
  48 #include "graphite-ppl.h"
  49 #include "graphite.h"
  50 #include "graphite-poly.h"
  51 #include "graphite-scop-detection.h"
  52 #include "graphite-clast-to-gimple.h"
  53 #include "graphite-dependences.h"
  54
  55 /* This flag is set when an error occurred during the translation of
  56    CLAST to Gimple.  */
  57 static bool gloog_error;
  58
  59 /* Verifies properties that GRAPHITE should maintain during translation.  */
  60
  61 static inline void
  62 graphite_verify (void)
  63 {
  64 #ifdef ENABLE_CHECKING
  65   verify_loop_structure ();
  66   verify_dominators (CDI_DOMINATORS);
  67   verify_dominators (CDI_POST_DOMINATORS);
  68   verify_ssa (false);
  69   verify_loop_closed_ssa ();
  70 #endif
  71 }
  72
  73 /* Stores the INDEX in a vector for a given clast NAME.  */
  74
  75 typedef struct clast_name_index {
  76   int index;
  77   const char *name;
  78 } *clast_name_index_p;
  79
  80 /* Returns a pointer to a new element of type clast_name_index_p built
  81    from NAME and INDEX.  */
  82
  83 static inline clast_name_index_p
  84 new_clast_name_index (const char *name, int index)
  85 {
  86   clast_name_index_p res = XNEW (struct clast_name_index);
  87
  88   res->name = name;
  89   res->index = index;
  90   return res;
  91 }
  92
  93 /* For a given clast NAME, returns -1 if it does not correspond to any
  94    parameter, or otherwise, returns the index in the PARAMS or
  95    SCATTERING_DIMENSIONS vector.  */
  96
  97 static inline int
  98 clast_name_to_index (const char *name, htab_t index_table)
  99 {
 100   struct clast_name_index tmp;
 101   PTR *slot;
 102
 103   tmp.name = name;
 104   slot = htab_find_slot (index_table, &tmp, NO_INSERT);
 105
 106   if (slot && *slot)
 107     return ((struct clast_name_index *) *slot)->index;
 108
 109   return -1;
 110 }
 111
 112 /* Records in INDEX_TABLE the INDEX for NAME.  */
 113
 114 static inline void
 115 save_clast_name_index (htab_t index_table, const char *name, int index)
 116 {
 117   struct clast_name_index tmp;
 118   PTR *slot;
 119
 120   tmp.name = name;
 121   slot = htab_find_slot (index_table, &tmp, INSERT);
 122
 123   if (slot)
 124     {
 125       if (*slot)
 126         free (*slot);
 127
 128       *slot = new_clast_name_index (name, index);
 129     }
 130 }
 131
 132 /* Print to stderr the element ELT.  */
 133
 134 static inline void
 135 debug_clast_name_index (clast_name_index_p elt)
 136 {
 137   fprintf (stderr, "(index = %d, name = %s)\n", elt->index, elt->name);
 138 }
 139
 140 /* Helper function for debug_rename_map.  */
 141
 142 static inline int
 143 debug_clast_name_indexes_1 (void **slot, void *s ATTRIBUTE_UNUSED)
 144 {
 145   struct clast_name_index *entry = (struct clast_name_index *) *slot;
 146   debug_clast_name_index (entry);
 147   return 1;
 148 }
 149
 150 /* Print to stderr all the elements of MAP.  */
 151
 152 void
 153 debug_clast_name_indexes (htab_t map)
 154 {
 155   htab_traverse (map, debug_clast_name_indexes_1, NULL);
 156 }
 157
 158 /* Computes a hash function for database element ELT.  */
 159
 160 static inline hashval_t
 161 clast_name_index_elt_info (const void *elt)
 162 {
 163   return htab_hash_pointer (((const struct clast_name_index *) elt)->name);
 164 }
 165
 166 /* Compares database elements E1 and E2.  */
 167
 168 static inline int
 169 eq_clast_name_indexes (const void *e1, const void *e2)
 170 {
 171   const struct clast_name_index *elt1 = (const struct clast_name_index *) e1;
 172   const struct clast_name_index *elt2 = (const struct clast_name_index *) e2;
 173
 174   return (elt1->name == elt2->name);
 175 }
 176
 177
 178 /* For a given loop DEPTH in the loop nest of the original black box
 179    PBB, return the old induction variable associated to that loop.  */
 180
 181 static inline tree
 182 pbb_to_depth_to_oldiv (poly_bb_p pbb, int depth)
 183 {
 184   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
 185   sese region = SCOP_REGION (PBB_SCOP (pbb));
 186   loop_p loop = gbb_loop_at_index (gbb, region, depth);
 187
 188   return loop->single_iv;
 189 }
 190
 191 /* For a given scattering dimension, return the new induction variable
 192    associated to it.  */
 193
 194 static inline tree
 195 newivs_to_depth_to_newiv (VEC (tree, heap) *newivs, int depth)
 196 {
 197   return VEC_index (tree, newivs, depth);
 198 }
 199
 200 \f
 201
 202 /* Returns the tree variable from the name NAME that was given in
 203    Cloog representation.  */
 204
 205 static tree
 206 clast_name_to_gcc (const char *name, sese region, VEC (tree, heap) *newivs,
 207                    htab_t newivs_index, htab_t params_index)
 208 {
 209   int index;
 210   VEC (tree, heap) *params = SESE_PARAMS (region);
 211
 212   if (params && params_index)
 213     {
 214       index = clast_name_to_index (name, params_index);
 215
 216       if (index >= 0)
 217         return VEC_index (tree, params, index);
 218     }
 219
 220   gcc_assert (newivs && newivs_index);
 221   index = clast_name_to_index (name, newivs_index);
 222   gcc_assert (index >= 0);
 223
 224   return newivs_to_depth_to_newiv (newivs, index);
 225 }
 226
 227 /* Returns the maximal precision type for expressions E1 and E2.  */
 228
 229 static inline tree
 230 max_precision_type (tree e1, tree e2)
 231 {
 232   tree type1 = TREE_TYPE (e1);
 233   tree type2 = TREE_TYPE (e2);
 234   return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
 235 }
 236
 237 static tree
 238 clast_to_gcc_expression (tree, struct clast_expr *, sese, VEC (tree, heap) *,
 239                          htab_t, htab_t);
 240
 241 /* Converts a Cloog reduction expression R with reduction operation OP
 242    to a GCC expression tree of type TYPE.  */
 243
 244 static tree
 245 clast_to_gcc_expression_red (tree type, enum tree_code op,
 246                              struct clast_reduction *r,
 247                              sese region, VEC (tree, heap) *newivs,
 248                              htab_t newivs_index, htab_t params_index)
 249 {
 250   int i;
 251   tree res = clast_to_gcc_expression (type, r->elts[0], region, newivs,
 252                                       newivs_index, params_index);
 253   tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type;
 254
 255   for (i = 1; i < r->n; i++)
 256     {
 257       tree t = clast_to_gcc_expression (operand_type, r->elts[i], region,
 258                                         newivs, newivs_index, params_index);
 259       res = fold_build2 (op, type, res, t);
 260     }
 261
 262   return res;
 263 }
 264
 265 /* Converts a Cloog AST expression E back to a GCC expression tree of
 266    type TYPE.  */
 267
 268 static tree
 269 clast_to_gcc_expression (tree type, struct clast_expr *e,
 270                          sese region, VEC (tree, heap) *newivs,
 271                          htab_t newivs_index, htab_t params_index)
 272 {
 273   switch (e->type)
 274     {
 275     case expr_term:
 276       {
 277         struct clast_term *t = (struct clast_term *) e;
 278
 279         if (t->var)
 280           {
 281             if (value_one_p (t->val))
 282               {
 283                 tree name = clast_name_to_gcc (t->var, region, newivs,
 284                                                newivs_index, params_index);
 285
 286                 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
 287                   name = fold_convert (sizetype, name);
 288
 289                 name = fold_convert (type, name);
 290                 return name;
 291               }
 292
 293             else if (value_mone_p (t->val))
 294               {
 295                 tree name = clast_name_to_gcc (t->var, region, newivs,
 296                                                newivs_index, params_index);
 297
 298                 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
 299                   name = fold_convert (sizetype, name);
 300
 301                 name = fold_convert (type, name);
 302
 303                 return fold_build1 (NEGATE_EXPR, type, name);
 304               }
 305             else
 306               {
 307                 tree name = clast_name_to_gcc (t->var, region, newivs,
 308                                                newivs_index, params_index);
 309                 tree cst = gmp_cst_to_tree (type, t->val);
 310
 311                 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
 312                   name = fold_convert (sizetype, name);
 313
 314                 name = fold_convert (type, name);
 315
 316                 if (!POINTER_TYPE_P (type))
 317                   return fold_build2 (MULT_EXPR, type, cst, name);
 318
 319                 gloog_error = true;
 320                 return cst;
 321               }
 322           }
 323         else
 324           return gmp_cst_to_tree (type, t->val);
 325       }
 326
 327     case expr_red:
 328       {
 329         struct clast_reduction *r = (struct clast_reduction *) e;
 330
 331         switch (r->type)
 332           {
 333           case clast_red_sum:
 334             return clast_to_gcc_expression_red
 335               (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
 336                r, region, newivs, newivs_index, params_index);
 337
 338           case clast_red_min:
 339             return clast_to_gcc_expression_red (type, MIN_EXPR, r, region,
 340                                                 newivs, newivs_index,
 341                                                 params_index);
 342
 343           case clast_red_max:
 344             return clast_to_gcc_expression_red (type, MAX_EXPR, r, region,
 345                                                 newivs, newivs_index,
 346                                                 params_index);
 347
 348           default:
 349             gcc_unreachable ();
 350           }
 351         break;
 352       }
 353
 354     case expr_bin:
 355       {
 356         struct clast_binary *b = (struct clast_binary *) e;
 357         struct clast_expr *lhs = (struct clast_expr *) b->LHS;
 358         tree tl = clast_to_gcc_expression (type, lhs, region, newivs,
 359                                            newivs_index, params_index);
 360         tree tr = gmp_cst_to_tree (type, b->RHS);
 361
 362         switch (b->type)
 363           {
 364           case clast_bin_fdiv:
 365             return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
 366
 367           case clast_bin_cdiv:
 368             return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
 369
 370           case clast_bin_div:
 371             return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
 372
 373           case clast_bin_mod:
 374             return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
 375
 376           default:
 377             gcc_unreachable ();
 378           }
 379       }
 380
 381     default:
 382       gcc_unreachable ();
 383     }
 384
 385   return NULL_TREE;
 386 }
 387
 388 /* Returns the type for the expression E.  */
 389
 390 static tree
 391 gcc_type_for_clast_expr (struct clast_expr *e,
 392                          sese region, VEC (tree, heap) *newivs,
 393                          htab_t newivs_index, htab_t params_index)
 394 {
 395   switch (e->type)
 396     {
 397     case expr_term:
 398       {
 399         struct clast_term *t = (struct clast_term *) e;
 400
 401         if (t->var)
 402           return TREE_TYPE (clast_name_to_gcc (t->var, region, newivs,
 403                                                newivs_index, params_index));
 404         else
 405           return NULL_TREE;
 406       }
 407
 408     case expr_red:
 409       {
 410         struct clast_reduction *r = (struct clast_reduction *) e;
 411
 412         if (r->n == 1)
 413           return gcc_type_for_clast_expr (r->elts[0], region, newivs,
 414                                           newivs_index, params_index);
 415         else
 416           {
 417             int i;
 418             for (i = 0; i < r->n; i++)
 419               {
 420                 tree type = gcc_type_for_clast_expr (r->elts[i], region,
 421                                                      newivs, newivs_index,
 422                                                      params_index);
 423                 if (type)
 424                   return type;
 425               }
 426             return NULL_TREE;
 427           }
 428       }
 429
 430     case expr_bin:
 431       {
 432         struct clast_binary *b = (struct clast_binary *) e;
 433         struct clast_expr *lhs = (struct clast_expr *) b->LHS;
 434         return gcc_type_for_clast_expr (lhs, region, newivs,
 435                                         newivs_index, params_index);
 436       }
 437
 438     default:
 439       gcc_unreachable ();
 440     }
 441
 442   return NULL_TREE;
 443 }
 444
 445 /* Returns the type for the equation CLEQ.  */
 446
 447 static tree
 448 gcc_type_for_clast_eq (struct clast_equation *cleq,
 449                        sese region, VEC (tree, heap) *newivs,
 450                        htab_t newivs_index, htab_t params_index)
 451 {
 452   tree type = gcc_type_for_clast_expr (cleq->LHS, region, newivs,
 453                                        newivs_index, params_index);
 454   if (type)
 455     return type;
 456
 457   return gcc_type_for_clast_expr (cleq->RHS, region, newivs, newivs_index,
 458                                   params_index);
 459 }
 460
 461 /* Translates a clast equation CLEQ to a tree.  */
 462
 463 static tree
 464 graphite_translate_clast_equation (sese region,
 465                                    struct clast_equation *cleq,
 466                                    VEC (tree, heap) *newivs,
 467                                    htab_t newivs_index, htab_t params_index)
 468 {
 469   enum tree_code comp;
 470   tree type = gcc_type_for_clast_eq (cleq, region, newivs, newivs_index,
 471                                      params_index);
 472   tree lhs = clast_to_gcc_expression (type, cleq->LHS, region, newivs,
 473                                       newivs_index, params_index);
 474   tree rhs = clast_to_gcc_expression (type, cleq->RHS, region, newivs,
 475                                       newivs_index, params_index);
 476
 477   if (cleq->sign == 0)
 478     comp = EQ_EXPR;
 479
 480   else if (cleq->sign > 0)
 481     comp = GE_EXPR;
 482
 483   else
 484     comp = LE_EXPR;
 485
 486   return fold_build2 (comp, boolean_type_node, lhs, rhs);
 487 }
 488
 489 /* Creates the test for the condition in STMT.  */
 490
 491 static tree
 492 graphite_create_guard_cond_expr (sese region, struct clast_guard *stmt,
 493                                  VEC (tree, heap) *newivs,
 494                                  htab_t newivs_index, htab_t params_index)
 495 {
 496   tree cond = NULL;
 497   int i;
 498
 499   for (i = 0; i < stmt->n; i++)
 500     {
 501       tree eq = graphite_translate_clast_equation (region, &stmt->eq[i],
 502                                                    newivs, newivs_index,
 503                                                    params_index);
 504
 505       if (cond)
 506         cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
 507       else
 508         cond = eq;
 509     }
 510
 511   return cond;
 512 }
 513
 514 /* Creates a new if region corresponding to Cloog's guard.  */
 515
 516 static edge
 517 graphite_create_new_guard (sese region, edge entry_edge,
 518                            struct clast_guard *stmt,
 519                            VEC (tree, heap) *newivs,
 520                            htab_t newivs_index, htab_t params_index)
 521 {
 522   tree cond_expr = graphite_create_guard_cond_expr (region, stmt, newivs,
 523                                                     newivs_index, params_index);
 524   edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
 525   return exit_edge;
 526 }
 527
 528 /* Walks a CLAST and returns the first statement in the body of a
 529    loop.  */
 530
 531 static struct clast_user_stmt *
 532 clast_get_body_of_loop (struct clast_stmt *stmt)
 533 {
 534   if (!stmt
 535       || CLAST_STMT_IS_A (stmt, stmt_user))
 536     return (struct clast_user_stmt *) stmt;
 537
 538   if (CLAST_STMT_IS_A (stmt, stmt_for))
 539     return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
 540
 541   if (CLAST_STMT_IS_A (stmt, stmt_guard))
 542     return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
 543
 544   if (CLAST_STMT_IS_A (stmt, stmt_block))
 545     return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
 546
 547   gcc_unreachable ();
 548 }
 549
 550 /* Given a CLOOG_IV, return the type that CLOOG_IV should have in GCC
 551    land.  The selected type is big enough to include the original loop
 552    iteration variable, but signed to work with the subtractions CLooG
 553    may have introduced.  If such a type is not available, we fail.
 554
 555    TODO: Do not always return long_long, but the smallest possible
 556    type, that still holds the original type.
 557
 558    TODO: Get the types using CLooG instead.  This enables further
 559    optimizations, but needs CLooG support.  */
 560
 561 static tree
 562 gcc_type_for_cloog_iv (const char *cloog_iv, gimple_bb_p gbb)
 563 {
 564   struct ivtype_map_elt_s tmp;
 565   PTR *slot;
 566
 567   tmp.cloog_iv = cloog_iv;
 568   slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
 569
 570   if (slot && *slot)
 571     {
 572       tree type = ((ivtype_map_elt) *slot)->type;
 573       int type_precision = TYPE_PRECISION (type);
 574
 575       /* Find the smallest signed type possible.  */
 576       if (!TYPE_UNSIGNED (type))
 577         {
 578           if (type_precision <= TYPE_PRECISION (integer_type_node))
 579             return integer_type_node;
 580
 581           if (type_precision <= TYPE_PRECISION (long_integer_type_node))
 582             return long_integer_type_node;
 583
 584           if (type_precision <= TYPE_PRECISION (long_long_integer_type_node))
 585             return long_long_integer_type_node;
 586
 587           gcc_unreachable ();
 588         }
 589
 590       if (type_precision < TYPE_PRECISION (integer_type_node))
 591         return integer_type_node;
 592
 593       if (type_precision < TYPE_PRECISION (long_integer_type_node))
 594         return long_integer_type_node;
 595
 596       if (type_precision < TYPE_PRECISION (long_long_integer_type_node))
 597         return long_long_integer_type_node;
 598
 599       /* There is no signed type available, that is large enough to hold the
 600          original value.  */
 601       gcc_unreachable ();
 602     }
 603
 604   return long_long_integer_type_node;
 605 }
 606
 607 /* Returns the induction variable for the loop that gets translated to
 608    STMT.  */
 609
 610 static tree
 611 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
 612 {
 613   struct clast_stmt *stmt = (struct clast_stmt *) stmt_for;
 614   struct clast_user_stmt *body = clast_get_body_of_loop (stmt);
 615   const char *cloog_iv = stmt_for->iterator;
 616   CloogStatement *cs = body->statement;
 617   poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
 618
 619   return gcc_type_for_cloog_iv (cloog_iv, PBB_BLACK_BOX (pbb));
 620 }
 621
 622 /* Creates a new LOOP corresponding to Cloog's STMT.  Inserts an
 623    induction variable for the new LOOP.  New LOOP is attached to CFG
 624    starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
 625    becomes the child loop of the OUTER_LOOP.  NEWIVS_INDEX binds
 626    CLooG's scattering name to the induction variable created for the
 627    loop of STMT.  The new induction variable is inserted in the NEWIVS
 628    vector.  */
 629
 630 static struct loop *
 631 graphite_create_new_loop (sese region, edge entry_edge,
 632                           struct clast_for *stmt,
 633                           loop_p outer, VEC (tree, heap) **newivs,
 634                           htab_t newivs_index, htab_t params_index)
 635 {
 636   tree type = gcc_type_for_iv_of_clast_loop (stmt);
 637   tree lb = clast_to_gcc_expression (type, stmt->LB, region, *newivs,
 638                                      newivs_index, params_index);
 639   tree ub = clast_to_gcc_expression (type, stmt->UB, region, *newivs,
 640                                      newivs_index, params_index);
 641   tree stride = gmp_cst_to_tree (type, stmt->stride);
 642   tree ivvar = create_tmp_var (type, "graphite_IV");
 643   tree iv, iv_after_increment;
 644   loop_p loop = create_empty_loop_on_edge
 645     (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
 646      outer ? outer : entry_edge->src->loop_father);
 647
 648   add_referenced_var (ivvar);
 649
 650   save_clast_name_index (newivs_index, stmt->iterator,
 651                          VEC_length (tree, *newivs));
 652   VEC_safe_push (tree, heap, *newivs, iv);
 653   return loop;
 654 }
 655
 656 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
 657    variables of the loops around GBB in SESE.  */
 658
 659 static void
 660 build_iv_mapping (htab_t map, sese region,
 661                   VEC (tree, heap) *newivs, htab_t newivs_index,
 662                   struct clast_user_stmt *user_stmt,
 663                   htab_t params_index)
 664 {
 665   struct clast_stmt *t;
 666   int index = 0;
 667   CloogStatement *cs = user_stmt->statement;
 668   poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
 669
 670   for (t = user_stmt->substitutions; t; t = t->next, index++)
 671     {
 672       struct clast_expr *expr = (struct clast_expr *)
 673        ((struct clast_assignment *)t)->RHS;
 674       tree type = gcc_type_for_clast_expr (expr, region, newivs,
 675                                            newivs_index, params_index);
 676       tree old_name = pbb_to_depth_to_oldiv (pbb, index);
 677       tree e = clast_to_gcc_expression (type, expr, region, newivs,
 678                                         newivs_index, params_index);
 679       set_rename (map, old_name, e);
 680     }
 681 }
 682
 683 /* Helper function for htab_traverse.  */
 684
 685 static int
 686 copy_renames (void **slot, void *s)
 687 {
 688   struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
 689   htab_t res = (htab_t) s;
 690   tree old_name = entry->old_name;
 691   tree expr = entry->expr;
 692   struct rename_map_elt_s tmp;
 693   PTR *x;
 694
 695   tmp.old_name = old_name;
 696   x = htab_find_slot (res, &tmp, INSERT);
 697
 698   if (x && !*x)
 699     *x = new_rename_map_elt (old_name, expr);
 700
 701   return 1;
 702 }
 703
 704 /* Construct bb_pbb_def with BB and PBB. */
 705
 706 static bb_pbb_def *
 707 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
 708 {
 709   bb_pbb_def *bb_pbb_p;
 710
 711   bb_pbb_p = XNEW (bb_pbb_def);
 712   bb_pbb_p->bb = bb;
 713   bb_pbb_p->pbb = pbb;
 714
 715   return bb_pbb_p;
 716 }
 717
 718 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING.  */
 719
 720 static void
 721 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
 722 {
 723   bb_pbb_def tmp;
 724   PTR *x;
 725
 726   tmp.bb = bb;
 727   x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
 728
 729   if (x && !*x)
 730     *x = new_bb_pbb_def (bb, pbb);
 731 }
 732
 733 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING.  */
 734
 735 static poly_bb_p
 736 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
 737 {
 738   bb_pbb_def tmp;
 739   PTR *slot;
 740
 741   tmp.bb = bb;
 742   slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
 743
 744   if (slot && *slot)
 745     return ((bb_pbb_def *) *slot)->pbb;
 746
 747   return NULL;
 748 }
 749
 750 /* Check data dependency in LOOP at scattering level LEVEL.
 751    BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
 752    mapping.  */
 753
 754 static bool
 755 dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level)
 756 {
 757   unsigned i,j;
 758   basic_block *bbs = get_loop_body_in_dom_order (loop);
 759
 760   for (i = 0; i < loop->num_nodes; i++)
 761     {
 762       poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
 763
 764       if (pbb1 == NULL)
 765        continue;
 766
 767       for (j = 0; j < loop->num_nodes; j++)
 768        {
 769          poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
 770
 771          if (pbb2 == NULL)
 772            continue;
 773
 774          if (dependency_between_pbbs_p (pbb1, pbb2, level))
 775            {
 776              free (bbs);
 777              return true;
 778            }
 779        }
 780     }
 781
 782   free (bbs);
 783
 784   return false;
 785 }
 786
 787 static edge
 788 translate_clast (sese, loop_p, struct clast_stmt *, edge, htab_t,
 789                  VEC (tree, heap) **, htab_t, htab_t, int, htab_t);
 790
 791 /* Translates a clast user statement STMT to gimple.
 792
 793    - REGION is the sese region we used to generate the scop.
 794    - NEXT_E is the edge where new generated code should be attached.
 795    - CONTEXT_LOOP is the loop in which the generated code will be placed
 796    - RENAME_MAP contains a set of tuples of new names associated to
 797      the original variables names.
 798    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 799    - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 800      the sese region.  */
 801 static edge
 802 translate_clast_user (sese region, struct clast_user_stmt *stmt, edge next_e,
 803                       htab_t rename_map, VEC (tree, heap) **newivs,
 804                       htab_t newivs_index, htab_t bb_pbb_mapping,
 805                       htab_t params_index)
 806 {
 807   gimple_bb_p gbb;
 808   basic_block new_bb;
 809   poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
 810   gbb = PBB_BLACK_BOX (pbb);
 811
 812   if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
 813     return next_e;
 814
 815   build_iv_mapping (rename_map, region, *newivs, newivs_index, stmt,
 816                     params_index);
 817   next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region,
 818                                            next_e, rename_map);
 819   new_bb = next_e->src;
 820   mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
 821   update_ssa (TODO_update_ssa);
 822
 823   return next_e;
 824 }
 825
 826 /* Creates a new if region protecting the loop to be executed, if the execution
 827    count is zero (lb > ub).  */
 828 static edge
 829 graphite_create_new_loop_guard (sese region, edge entry_edge,
 830                                 struct clast_for *stmt,
 831                                 VEC (tree, heap) *newivs,
 832                                 htab_t newivs_index, htab_t params_index)
 833 {
 834   tree cond_expr;
 835   edge exit_edge;
 836   tree type = gcc_type_for_iv_of_clast_loop (stmt);
 837   tree lb = clast_to_gcc_expression (type, stmt->LB, region, newivs,
 838                                      newivs_index, params_index);
 839   tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs,
 840                                      newivs_index, params_index);
 841
 842   /* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a
 843      loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this becomes
 844      2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
 845      However lb < ub + 1 is false, as expected.
 846      There might be a problem with cases where ub is 2^32.  */
 847   tree one;
 848   Value gmp_one;
 849   value_init (gmp_one);
 850   value_set_si (gmp_one, 1);
 851   one = gmp_cst_to_tree (type, gmp_one);
 852   value_clear (gmp_one);
 853
 854   ub = fold_build2 (PLUS_EXPR, type, ub, one);
 855   cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub);
 856
 857   exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
 858
 859   return exit_edge;
 860 }
 861
 862
 863 /* Create the loop for a clast for statement.
 864
 865    - REGION is the sese region we used to generate the scop.
 866    - NEXT_E is the edge where new generated code should be attached.
 867    - RENAME_MAP contains a set of tuples of new names associated to
 868      the original variables names.
 869    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 870    - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 871      the sese region.  */
 872 static edge
 873 translate_clast_for_loop (sese region, loop_p context_loop,
 874                           struct clast_for *stmt, edge next_e,
 875                           htab_t rename_map, VEC (tree, heap) **newivs,
 876                           htab_t newivs_index, htab_t bb_pbb_mapping,
 877                           int level, htab_t params_index)
 878 {
 879   struct loop *loop = graphite_create_new_loop (region, next_e, stmt,
 880                                                 context_loop, newivs,
 881                                                 newivs_index, params_index);
 882   edge last_e = single_exit (loop);
 883   edge to_body = single_succ_edge (loop->header);
 884   basic_block after = to_body->dest;
 885
 886   /* Create a basic block for loop close phi nodes.  */
 887   last_e = single_succ_edge (split_edge (last_e));
 888
 889   /* Translate the body of the loop.  */
 890   next_e = translate_clast (region, loop, stmt->body, to_body, rename_map,
 891                             newivs, newivs_index, bb_pbb_mapping, level + 1,
 892                             params_index);
 893   redirect_edge_succ_nodup (next_e, after);
 894   set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
 895
 896    /* Remove from rename_map all the tuples containing variables
 897       defined in loop's body.  */
 898   insert_loop_close_phis (rename_map, loop);
 899
 900   if (flag_loop_parallelize_all
 901       && !dependency_in_loop_p (loop, bb_pbb_mapping,
 902                                 get_scattering_level (level)))
 903     loop->can_be_parallel = true;
 904
 905   return last_e;
 906 }
 907
 908 /* Translates a clast for statement STMT to gimple.  First a guard is created
 909    protecting the loop, if it is executed zero times.  In this guard we create
 910    the real loop structure.
 911
 912    - REGION is the sese region we used to generate the scop.
 913    - NEXT_E is the edge where new generated code should be attached.
 914    - RENAME_MAP contains a set of tuples of new names associated to
 915      the original variables names.
 916    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 917    - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 918      the sese region.  */
 919 static edge
 920 translate_clast_for (sese region, loop_p context_loop, struct clast_for *stmt,
 921                      edge next_e, htab_t rename_map, VEC (tree, heap) **newivs,
 922                      htab_t newivs_index, htab_t bb_pbb_mapping, int level,
 923                      htab_t params_index)
 924 {
 925   edge last_e = graphite_create_new_loop_guard (region, next_e, stmt, *newivs,
 926                                            newivs_index, params_index);
 927
 928   edge true_e = get_true_edge_from_guard_bb (next_e->dest);
 929   edge false_e = get_false_edge_from_guard_bb (next_e->dest);
 930   edge exit_true_e = single_succ_edge (true_e->dest);
 931   edge exit_false_e = single_succ_edge (false_e->dest);
 932
 933   htab_t before_guard = htab_create (10, rename_map_elt_info,
 934                                      eq_rename_map_elts, free);
 935   htab_traverse (rename_map, copy_renames, before_guard);
 936
 937   next_e = translate_clast_for_loop (region, context_loop, stmt, true_e,
 938                                      rename_map, newivs,
 939                                      newivs_index, bb_pbb_mapping, level,
 940                                      params_index);
 941
 942   insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
 943                      before_guard, rename_map);
 944
 945   htab_delete (before_guard);
 946
 947   return last_e;
 948 }
 949
 950 /* Translates a clast guard statement STMT to gimple.
 951
 952    - REGION is the sese region we used to generate the scop.
 953    - NEXT_E is the edge where new generated code should be attached.
 954    - CONTEXT_LOOP is the loop in which the generated code will be placed
 955    - RENAME_MAP contains a set of tuples of new names associated to
 956      the original variables names.
 957    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 958    - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 959      the sese region.  */
 960 static edge
 961 translate_clast_guard (sese region, loop_p context_loop,
 962                        struct clast_guard *stmt, edge next_e,
 963                        htab_t rename_map, VEC (tree, heap) **newivs,
 964                        htab_t newivs_index, htab_t bb_pbb_mapping, int level,
 965                        htab_t params_index)
 966 {
 967   edge last_e = graphite_create_new_guard (region, next_e, stmt, *newivs,
 968                                            newivs_index, params_index);
 969
 970   edge true_e = get_true_edge_from_guard_bb (next_e->dest);
 971   edge false_e = get_false_edge_from_guard_bb (next_e->dest);
 972   edge exit_true_e = single_succ_edge (true_e->dest);
 973   edge exit_false_e = single_succ_edge (false_e->dest);
 974
 975   htab_t before_guard = htab_create (10, rename_map_elt_info,
 976                                      eq_rename_map_elts, free);
 977   htab_traverse (rename_map, copy_renames, before_guard);
 978
 979   next_e = translate_clast (region, context_loop, stmt->then, true_e,
 980                             rename_map, newivs, newivs_index, bb_pbb_mapping,
 981                             level, params_index);
 982
 983   insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
 984                      before_guard, rename_map);
 985
 986   htab_delete (before_guard);
 987
 988   return last_e;
 989 }
 990
 991 /* Translates a CLAST statement STMT to GCC representation in the
 992    context of a SESE.
 993
 994    - NEXT_E is the edge where new generated code should be attached.
 995    - CONTEXT_LOOP is the loop in which the generated code will be placed
 996    - RENAME_MAP contains a set of tuples of new names associated to
 997      the original variables names.
 998    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
 999 static edge
1000 translate_clast (sese region, loop_p context_loop, struct clast_stmt *stmt,
1001                  edge next_e, htab_t rename_map, VEC (tree, heap) **newivs,
1002                  htab_t newivs_index, htab_t bb_pbb_mapping, int level,
1003                  htab_t params_index)
1004 {
1005   if (!stmt)
1006     return next_e;
1007
1008   if (CLAST_STMT_IS_A (stmt, stmt_root))
1009     ; /* Do nothing.  */
1010
1011   else if (CLAST_STMT_IS_A (stmt, stmt_user))
1012     next_e = translate_clast_user (region, (struct clast_user_stmt *) stmt,
1013                                    next_e, rename_map, newivs, newivs_index,
1014                                    bb_pbb_mapping, params_index);
1015
1016   else if (CLAST_STMT_IS_A (stmt, stmt_for))
1017     next_e = translate_clast_for (region, context_loop,
1018                                   (struct clast_for *) stmt, next_e,
1019                                   rename_map, newivs, newivs_index,
1020                                   bb_pbb_mapping, level, params_index);
1021
1022   else if (CLAST_STMT_IS_A (stmt, stmt_guard))
1023     next_e = translate_clast_guard (region, context_loop,
1024                                     (struct clast_guard *) stmt, next_e,
1025                                     rename_map, newivs, newivs_index,
1026                                     bb_pbb_mapping, level, params_index);
1027
1028   else if (CLAST_STMT_IS_A (stmt, stmt_block))
1029     next_e = translate_clast (region, context_loop,
1030                               ((struct clast_block *) stmt)->body,
1031                               next_e, rename_map, newivs, newivs_index,
1032                               bb_pbb_mapping, level, params_index);
1033   else
1034     gcc_unreachable();
1035
1036   recompute_all_dominators ();
1037   graphite_verify ();
1038
1039   return translate_clast (region, context_loop, stmt->next, next_e,
1040                           rename_map, newivs, newivs_index,
1041                           bb_pbb_mapping, level, params_index);
1042 }
1043
1044 /* Returns the first cloog name used in EXPR.  */
1045
1046 static const char *
1047 find_cloog_iv_in_expr (struct clast_expr *expr)
1048 {
1049   struct clast_term *term = (struct clast_term *) expr;
1050   struct clast_reduction *red;
1051   int i;
1052
1053   if (expr->type == expr_term)
1054     return term->var;
1055
1056   if (expr->type != expr_red)
1057     return NULL;
1058
1059   red = (struct clast_reduction *) expr;
1060   for (i = 0; i < red->n; i++)
1061     {
1062       const char *res = find_cloog_iv_in_expr (red->elts[i]);
1063
1064       if (res)
1065         return res;
1066     }
1067
1068   return NULL;
1069 }
1070
1071 /* Build for USER_STMT a map between the CLAST induction variables and
1072    the corresponding GCC old induction variables.  This information is
1073    stored on each GRAPHITE_BB.  */
1074
1075 static void
1076 compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt)
1077 {
1078   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1079   struct clast_stmt *t;
1080   int index = 0;
1081
1082   for (t = user_stmt->substitutions; t; t = t->next, index++)
1083     {
1084       PTR *slot;
1085       struct ivtype_map_elt_s tmp;
1086       struct clast_expr *expr = (struct clast_expr *)
1087         ((struct clast_assignment *)t)->RHS;
1088
1089       /* Create an entry (clast_var, type).  */
1090       tmp.cloog_iv = find_cloog_iv_in_expr (expr);
1091       if (!tmp.cloog_iv)
1092         continue;
1093
1094       slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
1095
1096       if (slot && !*slot)
1097         {
1098           tree oldiv = pbb_to_depth_to_oldiv (pbb, index);
1099           tree type = TREE_TYPE (oldiv);
1100           *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
1101         }
1102     }
1103 }
1104
1105 /* Walk the CLAST tree starting from STMT and build for each
1106    clast_user_stmt a map between the CLAST induction variables and the
1107    corresponding GCC old induction variables.  This information is
1108    stored on each GRAPHITE_BB.  */
1109
1110 static void
1111 compute_cloog_iv_types (struct clast_stmt *stmt)
1112 {
1113   if (!stmt)
1114     return;
1115
1116   if (CLAST_STMT_IS_A (stmt, stmt_root))
1117     goto next;
1118
1119   if (CLAST_STMT_IS_A (stmt, stmt_user))
1120     {
1121       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
1122       poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
1123       gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1124
1125       if (!GBB_CLOOG_IV_TYPES (gbb))
1126         GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
1127                                                 eq_ivtype_map_elts, free);
1128
1129       compute_cloog_iv_types_1 (pbb, (struct clast_user_stmt *) stmt);
1130       goto next;
1131     }
1132
1133   if (CLAST_STMT_IS_A (stmt, stmt_for))
1134     {
1135       struct clast_stmt *s = ((struct clast_for *) stmt)->body;
1136       compute_cloog_iv_types (s);
1137       goto next;
1138     }
1139
1140   if (CLAST_STMT_IS_A (stmt, stmt_guard))
1141     {
1142       struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
1143       compute_cloog_iv_types (s);
1144       goto next;
1145     }
1146
1147   if (CLAST_STMT_IS_A (stmt, stmt_block))
1148     {
1149       struct clast_stmt *s = ((struct clast_block *) stmt)->body;
1150       compute_cloog_iv_types (s);
1151       goto next;
1152     }
1153
1154   gcc_unreachable ();
1155
1156  next:
1157   compute_cloog_iv_types (stmt->next);
1158 }
1159
1160 /* Free the SCATTERING domain list.  */
1161
1162 static void
1163 free_scattering (CloogDomainList *scattering)
1164 {
1165   while (scattering)
1166     {
1167       CloogDomain *dom = cloog_domain (scattering);
1168       CloogDomainList *next = cloog_next_domain (scattering);
1169
1170       cloog_domain_free (dom);
1171       free (scattering);
1172       scattering = next;
1173     }
1174 }
1175
1176 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1177    Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1178    from 0 to scop_nb_loops (scop).  */
1179
1180 static void
1181 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1182 {
1183   sese region = SCOP_REGION (scop);
1184   int i;
1185   int nb_iterators = scop_max_loop_depth (scop);
1186   int nb_scattering = cloog_program_nb_scattdims (prog);
1187   int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1188   char **iterators = XNEWVEC (char *, nb_iterators * 2);
1189   char **scattering = XNEWVEC (char *, nb_scattering);
1190   char **parameters= XNEWVEC (char *, nb_parameters);
1191
1192   cloog_program_set_names (prog, cloog_names_malloc ());
1193
1194   for (i = 0; i < nb_parameters; i++)
1195     {
1196       tree param = VEC_index (tree, SESE_PARAMS(region), i);
1197       const char *name = get_name (param);
1198       int len;
1199
1200       if (!name)
1201         name = "T";
1202
1203       len = strlen (name);
1204       len += 17;
1205       parameters[i] = XNEWVEC (char, len + 1);
1206       snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1207     }
1208
1209   cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1210   cloog_names_set_parameters (cloog_program_names (prog), parameters);
1211
1212   for (i = 0; i < nb_iterators; i++)
1213     {
1214       int len = 4 + 16;
1215       iterators[i] = XNEWVEC (char, len);
1216       snprintf (iterators[i], len, "git_%d", i);
1217     }
1218
1219   cloog_names_set_nb_iterators (cloog_program_names (prog),
1220                                 nb_iterators);
1221   cloog_names_set_iterators (cloog_program_names (prog),
1222                              iterators);
1223
1224   for (i = 0; i < nb_scattering; i++)
1225     {
1226       int len = 5 + 16;
1227       scattering[i] = XNEWVEC (char, len);
1228       snprintf (scattering[i], len, "scat_%d", i);
1229     }
1230
1231   cloog_names_set_nb_scattering (cloog_program_names (prog),
1232                                  nb_scattering);
1233   cloog_names_set_scattering (cloog_program_names (prog),
1234                               scattering);
1235 }
1236
1237 /* Build cloog program for SCoP.  */
1238
1239 static void
1240 build_cloog_prog (scop_p scop, CloogProgram *prog)
1241 {
1242   int i;
1243   int max_nb_loops = scop_max_loop_depth (scop);
1244   poly_bb_p pbb;
1245   CloogLoop *loop_list = NULL;
1246   CloogBlockList *block_list = NULL;
1247   CloogDomainList *scattering = NULL;
1248   int nbs = 2 * max_nb_loops + 1;
1249   int *scaldims;
1250
1251   cloog_program_set_context
1252     (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop)));
1253   nbs = unify_scattering_dimensions (scop);
1254   scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1255   cloog_program_set_nb_scattdims (prog, nbs);
1256   initialize_cloog_names (scop, prog);
1257
1258   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1259     {
1260       CloogStatement *stmt;
1261       CloogBlock *block;
1262
1263       /* Dead code elimination: when the domain of a PBB is empty,
1264          don't generate code for the PBB.  */
1265       if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1266         continue;
1267
1268       /* Build the new statement and its block.  */
1269       stmt = cloog_statement_alloc (pbb_index (pbb));
1270       block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1271       cloog_statement_set_usr (stmt, pbb);
1272
1273       /* Build loop list.  */
1274       {
1275         CloogLoop *new_loop_list = cloog_loop_malloc ();
1276         cloog_loop_set_next (new_loop_list, loop_list);
1277         cloog_loop_set_domain
1278           (new_loop_list,
1279            new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb)));
1280         cloog_loop_set_block (new_loop_list, block);
1281         loop_list = new_loop_list;
1282       }
1283
1284       /* Build block list.  */
1285       {
1286         CloogBlockList *new_block_list = cloog_block_list_malloc ();
1287
1288         cloog_block_list_set_next (new_block_list, block_list);
1289         cloog_block_list_set_block (new_block_list, block);
1290         block_list = new_block_list;
1291       }
1292
1293       /* Build scattering list.  */
1294       {
1295         /* XXX: Replace with cloog_domain_list_alloc(), when available.  */
1296         CloogDomainList *new_scattering
1297           = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
1298         ppl_Polyhedron_t scat;
1299         CloogDomain *dom;
1300
1301         scat = PBB_TRANSFORMED_SCATTERING (pbb);
1302         dom = new_Cloog_Domain_from_ppl_Polyhedron (scat);
1303
1304         cloog_set_next_domain (new_scattering, scattering);
1305         cloog_set_domain (new_scattering, dom);
1306         scattering = new_scattering;
1307       }
1308     }
1309
1310   cloog_program_set_loop (prog, loop_list);
1311   cloog_program_set_blocklist (prog, block_list);
1312
1313   for (i = 0; i < nbs; i++)
1314     scaldims[i] = 0 ;
1315
1316   cloog_program_set_scaldims (prog, scaldims);
1317
1318   /* Extract scalar dimensions to simplify the code generation problem.  */
1319   cloog_program_extract_scalars (prog, scattering);
1320
1321   /* Apply scattering.  */
1322   cloog_program_scatter (prog, scattering);
1323   free_scattering (scattering);
1324
1325   /* Iterators corresponding to scalar dimensions have to be extracted.  */
1326   cloog_names_scalarize (cloog_program_names (prog), nbs,
1327                          cloog_program_scaldims (prog));
1328
1329   /* Free blocklist.  */
1330   {
1331     CloogBlockList *next = cloog_program_blocklist (prog);
1332
1333     while (next)
1334       {
1335         CloogBlockList *toDelete = next;
1336         next = cloog_block_list_next (next);
1337         cloog_block_list_set_next (toDelete, NULL);
1338         cloog_block_list_set_block (toDelete, NULL);
1339         cloog_block_list_free (toDelete);
1340       }
1341     cloog_program_set_blocklist (prog, NULL);
1342   }
1343 }
1344
1345 /* Return the options that will be used in GLOOG.  */
1346
1347 static CloogOptions *
1348 set_cloog_options (void)
1349 {
1350   CloogOptions *options = cloog_options_malloc ();
1351
1352   /* Change cloog output language to C.  If we do use FORTRAN instead, cloog
1353      will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1354      we pass an incomplete program to cloog.  */
1355   options->language = LANGUAGE_C;
1356
1357   /* Enable complex equality spreading: removes dummy statements
1358      (assignments) in the generated code which repeats the
1359      substitution equations for statements.  This is useless for
1360      GLooG.  */
1361   options->esp = 1;
1362
1363   /* Enable C pretty-printing mode: normalizes the substitution
1364      equations for statements.  */
1365   options->cpp = 1;
1366
1367   /* Allow cloog to build strides with a stride width different to one.
1368      This example has stride = 4:
1369
1370      for (i = 0; i < 20; i += 4)
1371        A  */
1372   options->strides = 1;
1373
1374   /* Disable optimizations and make cloog generate source code closer to the
1375      input.  This is useful for debugging,  but later we want the optimized
1376      code.
1377
1378      XXX: We can not disable optimizations, as loop blocking is not working
1379      without them.  */
1380   if (0)
1381     {
1382       options->f = -1;
1383       options->l = INT_MAX;
1384     }
1385
1386   return options;
1387 }
1388
1389 /* Prints STMT to STDERR.  */
1390
1391 void
1392 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1393 {
1394   CloogOptions *options = set_cloog_options ();
1395
1396   pprint (file, stmt, 0, options);
1397   cloog_options_free (options);
1398 }
1399
1400 /* Prints STMT to STDERR.  */
1401
1402 void
1403 debug_clast_stmt (struct clast_stmt *stmt)
1404 {
1405   print_clast_stmt (stderr, stmt);
1406 }
1407
1408 /* Translate SCOP to a CLooG program and clast.  These two
1409    representations should be freed together: a clast cannot be used
1410    without a program.  */
1411
1412 cloog_prog_clast
1413 scop_to_clast (scop_p scop)
1414 {
1415   CloogOptions *options = set_cloog_options ();
1416   cloog_prog_clast pc;
1417
1418   /* Connect new cloog prog generation to graphite.  */
1419   pc.prog = cloog_program_malloc ();
1420   build_cloog_prog (scop, pc.prog);
1421   pc.prog = cloog_program_generate (pc.prog, options);
1422   pc.stmt = cloog_clast_create (pc.prog, options);
1423
1424   cloog_options_free (options);
1425   return pc;
1426 }
1427
1428 /* Prints to FILE the code generated by CLooG for SCOP.  */
1429
1430 void
1431 print_generated_program (FILE *file, scop_p scop)
1432 {
1433   CloogOptions *options = set_cloog_options ();
1434   cloog_prog_clast pc = scop_to_clast (scop);
1435
1436   fprintf (file, "       (prog: \n");
1437   cloog_program_print (file, pc.prog);
1438   fprintf (file, "       )\n");
1439
1440   fprintf (file, "       (clast: \n");
1441   pprint (file, pc.stmt, 0, options);
1442   fprintf (file, "       )\n");
1443
1444   cloog_options_free (options);
1445   cloog_clast_free (pc.stmt);
1446   cloog_program_free (pc.prog);
1447 }
1448
1449 /* Prints to STDERR the code generated by CLooG for SCOP.  */
1450
1451 void
1452 debug_generated_program (scop_p scop)
1453 {
1454   print_generated_program (stderr, scop);
1455 }
1456
1457 /* Add CLooG names to parameter index.  The index is used to translate
1458    back from CLooG names to GCC trees.  */
1459
1460 static void
1461 create_params_index (htab_t index_table, CloogProgram *prog) {
1462   CloogNames* names = cloog_program_names (prog);
1463   int nb_parameters = cloog_names_nb_parameters (names);
1464   char **parameters = cloog_names_parameters (names);
1465   int i;
1466
1467   for (i = 0; i < nb_parameters; i++)
1468     save_clast_name_index (index_table, parameters[i], i);
1469 }
1470
1471 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1472    the given SCOP.  Return true if code generation succeeded.
1473    BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1474 */
1475
1476 bool
1477 gloog (scop_p scop, VEC (scop_p, heap) *scops, htab_t bb_pbb_mapping)
1478 {
1479   VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1480   loop_p context_loop;
1481   sese region = SCOP_REGION (scop);
1482   ifsese if_region = NULL;
1483   htab_t rename_map, newivs_index, params_index;
1484   cloog_prog_clast pc;
1485   int i;
1486
1487   timevar_push (TV_GRAPHITE_CODE_GEN);
1488   gloog_error = false;
1489
1490   pc = scop_to_clast (scop);
1491
1492   if (dump_file && (dump_flags & TDF_DETAILS))
1493     {
1494       fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1495       print_clast_stmt (dump_file, pc.stmt);
1496       fprintf (dump_file, "\n");
1497     }
1498
1499   recompute_all_dominators ();
1500   graphite_verify ();
1501
1502   if_region = move_sese_in_condition (region);
1503   sese_insert_phis_for_liveouts (region,
1504                                  if_region->region->exit->src,
1505                                  if_region->false_region->exit,
1506                                  if_region->true_region->exit);
1507   recompute_all_dominators ();
1508   graphite_verify ();
1509
1510   context_loop = SESE_ENTRY (region)->src->loop_father;
1511   compute_cloog_iv_types (pc.stmt);
1512   rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
1513   newivs_index = htab_create (10, clast_name_index_elt_info,
1514                               eq_clast_name_indexes, free);
1515   params_index = htab_create (10, clast_name_index_elt_info,
1516                               eq_clast_name_indexes, free);
1517
1518   create_params_index (params_index, pc.prog);
1519
1520   translate_clast (region, context_loop, pc.stmt,
1521                    if_region->true_region->entry,
1522                    rename_map, &newivs, newivs_index,
1523                    bb_pbb_mapping, 1, params_index);
1524   graphite_verify ();
1525   sese_adjust_liveout_phis (region, rename_map,
1526                             if_region->region->exit->src,
1527                             if_region->false_region->exit,
1528                             if_region->true_region->exit);
1529   scev_reset_htab ();
1530   rename_nb_iterations (rename_map);
1531
1532   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1533     rename_sese_parameters (rename_map, SCOP_REGION (scop));
1534
1535   recompute_all_dominators ();
1536   graphite_verify ();
1537
1538   if (gloog_error)
1539     set_ifsese_condition (if_region, integer_zero_node);
1540
1541   free (if_region->true_region);
1542   free (if_region->region);
1543   free (if_region);
1544
1545   htab_delete (rename_map);
1546   htab_delete (newivs_index);
1547   htab_delete (params_index);
1548   VEC_free (tree, heap, newivs);
1549   cloog_clast_free (pc.stmt);
1550   cloog_program_free (pc.prog);
1551   timevar_pop (TV_GRAPHITE_CODE_GEN);
1552
1553   if (dump_file && (dump_flags & TDF_DETAILS))
1554     {
1555       loop_p loop;
1556       loop_iterator li;
1557       int num_no_dependency = 0;
1558
1559       FOR_EACH_LOOP (li, loop, 0)
1560         if (loop->can_be_parallel)
1561           num_no_dependency++;
1562
1563       fprintf (dump_file, "\n%d loops carried no dependency.\n",
1564                num_no_dependency);
1565     }
1566
1567   return !gloog_error;
1568 }
1569
1570 #endif