gcc/graphite-clast-to-gimple.c

   1 /* Translation of CLAST (CLooG AST) to Gimple.
   2    Copyright (C) 2009, 2010 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 /* Java does not initialize long_long_integer_type_node.  */
 551 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
 552
 553 /* Given a CLOOG_IV, return the type that CLOOG_IV should have in GCC
 554    land.  The selected type is big enough to include the original loop
 555    iteration variable, but signed to work with the subtractions CLooG
 556    may have introduced.  If such a type is not available, we fail.
 557
 558    TODO: Do not always return long_long, but the smallest possible
 559    type, that still holds the original type.
 560
 561    TODO: Get the types using CLooG instead.  This enables further
 562    optimizations, but needs CLooG support.  */
 563
 564 static tree
 565 gcc_type_for_cloog_iv (const char *cloog_iv, gimple_bb_p gbb)
 566 {
 567   struct ivtype_map_elt_s tmp;
 568   PTR *slot;
 569
 570   tmp.cloog_iv = cloog_iv;
 571   slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
 572
 573   if (slot && *slot)
 574     {
 575       tree type = ((ivtype_map_elt) *slot)->type;
 576       int type_precision = TYPE_PRECISION (type);
 577
 578       /* Find the smallest signed type possible.  */
 579       if (!TYPE_UNSIGNED (type))
 580         {
 581           if (type_precision <= TYPE_PRECISION (integer_type_node))
 582             return integer_type_node;
 583
 584           if (type_precision <= TYPE_PRECISION (long_integer_type_node))
 585             return long_integer_type_node;
 586
 587           if (type_precision <= TYPE_PRECISION (my_long_long))
 588             return my_long_long;
 589
 590           gcc_unreachable ();
 591         }
 592
 593       if (type_precision < TYPE_PRECISION (integer_type_node))
 594         return integer_type_node;
 595
 596       if (type_precision < TYPE_PRECISION (long_integer_type_node))
 597         return long_integer_type_node;
 598
 599       if (type_precision < TYPE_PRECISION (my_long_long))
 600         return my_long_long;
 601
 602       /* There is no signed type available, that is large enough to hold the
 603          original value.  */
 604       gcc_unreachable ();
 605     }
 606
 607   return my_long_long;
 608 }
 609
 610 #undef my_long_long
 611
 612 /* Returns the induction variable for the loop that gets translated to
 613    STMT.  */
 614
 615 static tree
 616 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
 617 {
 618   struct clast_stmt *stmt = (struct clast_stmt *) stmt_for;
 619   struct clast_user_stmt *body = clast_get_body_of_loop (stmt);
 620   const char *cloog_iv = stmt_for->iterator;
 621   CloogStatement *cs = body->statement;
 622   poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
 623
 624   return gcc_type_for_cloog_iv (cloog_iv, PBB_BLACK_BOX (pbb));
 625 }
 626
 627 /* Creates a new LOOP corresponding to Cloog's STMT.  Inserts an
 628    induction variable for the new LOOP.  New LOOP is attached to CFG
 629    starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
 630    becomes the child loop of the OUTER_LOOP.  NEWIVS_INDEX binds
 631    CLooG's scattering name to the induction variable created for the
 632    loop of STMT.  The new induction variable is inserted in the NEWIVS
 633    vector.  */
 634
 635 static struct loop *
 636 graphite_create_new_loop (sese region, edge entry_edge,
 637                           struct clast_for *stmt,
 638                           loop_p outer, VEC (tree, heap) **newivs,
 639                           htab_t newivs_index, htab_t params_index)
 640 {
 641   tree type = gcc_type_for_iv_of_clast_loop (stmt);
 642   tree lb = clast_to_gcc_expression (type, stmt->LB, region, *newivs,
 643                                      newivs_index, params_index);
 644   tree ub = clast_to_gcc_expression (type, stmt->UB, region, *newivs,
 645                                      newivs_index, params_index);
 646   tree stride = gmp_cst_to_tree (type, stmt->stride);
 647   tree ivvar = create_tmp_var (type, "graphite_IV");
 648   tree iv, iv_after_increment;
 649   loop_p loop = create_empty_loop_on_edge
 650     (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
 651      outer ? outer : entry_edge->src->loop_father);
 652
 653   add_referenced_var (ivvar);
 654
 655   save_clast_name_index (newivs_index, stmt->iterator,
 656                          VEC_length (tree, *newivs));
 657   VEC_safe_push (tree, heap, *newivs, iv);
 658   return loop;
 659 }
 660
 661 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
 662    variables of the loops around GBB in SESE.  */
 663
 664 static void
 665 build_iv_mapping (htab_t map, sese region,
 666                   VEC (tree, heap) *newivs, htab_t newivs_index,
 667                   struct clast_user_stmt *user_stmt,
 668                   htab_t params_index)
 669 {
 670   struct clast_stmt *t;
 671   int index = 0;
 672   CloogStatement *cs = user_stmt->statement;
 673   poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
 674
 675   for (t = user_stmt->substitutions; t; t = t->next, index++)
 676     {
 677       struct clast_expr *expr = (struct clast_expr *)
 678        ((struct clast_assignment *)t)->RHS;
 679       tree type = gcc_type_for_clast_expr (expr, region, newivs,
 680                                            newivs_index, params_index);
 681       tree old_name = pbb_to_depth_to_oldiv (pbb, index);
 682       tree e = clast_to_gcc_expression (type, expr, region, newivs,
 683                                         newivs_index, params_index);
 684       set_rename (map, old_name, e);
 685     }
 686 }
 687
 688 /* Helper function for htab_traverse.  */
 689
 690 static int
 691 copy_renames (void **slot, void *s)
 692 {
 693   struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
 694   htab_t res = (htab_t) s;
 695   tree old_name = entry->old_name;
 696   tree expr = entry->expr;
 697   struct rename_map_elt_s tmp;
 698   PTR *x;
 699
 700   tmp.old_name = old_name;
 701   x = htab_find_slot (res, &tmp, INSERT);
 702
 703   if (x && !*x)
 704     *x = new_rename_map_elt (old_name, expr);
 705
 706   return 1;
 707 }
 708
 709 /* Construct bb_pbb_def with BB and PBB. */
 710
 711 static bb_pbb_def *
 712 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
 713 {
 714   bb_pbb_def *bb_pbb_p;
 715
 716   bb_pbb_p = XNEW (bb_pbb_def);
 717   bb_pbb_p->bb = bb;
 718   bb_pbb_p->pbb = pbb;
 719
 720   return bb_pbb_p;
 721 }
 722
 723 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING.  */
 724
 725 static void
 726 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
 727 {
 728   bb_pbb_def tmp;
 729   PTR *x;
 730
 731   tmp.bb = bb;
 732   x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
 733
 734   if (x && !*x)
 735     *x = new_bb_pbb_def (bb, pbb);
 736 }
 737
 738 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING.  */
 739
 740 static poly_bb_p
 741 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
 742 {
 743   bb_pbb_def tmp;
 744   PTR *slot;
 745
 746   tmp.bb = bb;
 747   slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
 748
 749   if (slot && *slot)
 750     return ((bb_pbb_def *) *slot)->pbb;
 751
 752   return NULL;
 753 }
 754
 755 /* Check data dependency in LOOP at scattering level LEVEL.
 756    BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
 757    mapping.  */
 758
 759 static bool
 760 dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level)
 761 {
 762   unsigned i,j;
 763   basic_block *bbs = get_loop_body_in_dom_order (loop);
 764
 765   for (i = 0; i < loop->num_nodes; i++)
 766     {
 767       poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
 768
 769       if (pbb1 == NULL)
 770        continue;
 771
 772       for (j = 0; j < loop->num_nodes; j++)
 773        {
 774          poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
 775
 776          if (pbb2 == NULL)
 777            continue;
 778
 779          if (dependency_between_pbbs_p (pbb1, pbb2, level))
 780            {
 781              free (bbs);
 782              return true;
 783            }
 784        }
 785     }
 786
 787   free (bbs);
 788
 789   return false;
 790 }
 791
 792 static edge
 793 translate_clast (sese, loop_p, struct clast_stmt *, edge, htab_t,
 794                  VEC (tree, heap) **, htab_t, htab_t, int, htab_t);
 795
 796 /* Translates a clast user statement STMT to gimple.
 797
 798    - REGION is the sese region we used to generate the scop.
 799    - NEXT_E is the edge where new generated code should be attached.
 800    - CONTEXT_LOOP is the loop in which the generated code will be placed
 801    - RENAME_MAP contains a set of tuples of new names associated to
 802      the original variables names.
 803    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 804    - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 805      the sese region.  */
 806 static edge
 807 translate_clast_user (sese region, struct clast_user_stmt *stmt, edge next_e,
 808                       htab_t rename_map, VEC (tree, heap) **newivs,
 809                       htab_t newivs_index, htab_t bb_pbb_mapping,
 810                       htab_t params_index)
 811 {
 812   gimple_bb_p gbb;
 813   basic_block new_bb;
 814   poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
 815   gbb = PBB_BLACK_BOX (pbb);
 816
 817   if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
 818     return next_e;
 819
 820   build_iv_mapping (rename_map, region, *newivs, newivs_index, stmt,
 821                     params_index);
 822   next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region,
 823                                            next_e, rename_map);
 824   new_bb = next_e->src;
 825   mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
 826   update_ssa (TODO_update_ssa);
 827
 828   return next_e;
 829 }
 830
 831 /* Creates a new if region protecting the loop to be executed, if the execution
 832    count is zero (lb > ub).  */
 833 static edge
 834 graphite_create_new_loop_guard (sese region, edge entry_edge,
 835                                 struct clast_for *stmt,
 836                                 VEC (tree, heap) *newivs,
 837                                 htab_t newivs_index, htab_t params_index)
 838 {
 839   tree cond_expr;
 840   edge exit_edge;
 841   tree type = gcc_type_for_iv_of_clast_loop (stmt);
 842   tree lb = clast_to_gcc_expression (type, stmt->LB, region, newivs,
 843                                      newivs_index, params_index);
 844   tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs,
 845                                      newivs_index, params_index);
 846
 847   /* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a
 848      loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this becomes
 849      2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
 850      However lb < ub + 1 is false, as expected.
 851      There might be a problem with cases where ub is 2^32.  */
 852   tree one;
 853   Value gmp_one;
 854   value_init (gmp_one);
 855   value_set_si (gmp_one, 1);
 856   one = gmp_cst_to_tree (type, gmp_one);
 857   value_clear (gmp_one);
 858
 859   ub = fold_build2 (PLUS_EXPR, type, ub, one);
 860   cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub);
 861
 862   exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
 863
 864   return exit_edge;
 865 }
 866
 867
 868 /* Create the loop for a clast for statement.
 869
 870    - REGION is the sese region we used to generate the scop.
 871    - NEXT_E is the edge where new generated code should be attached.
 872    - RENAME_MAP contains a set of tuples of new names associated to
 873      the original variables names.
 874    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 875    - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 876      the sese region.  */
 877 static edge
 878 translate_clast_for_loop (sese region, loop_p context_loop,
 879                           struct clast_for *stmt, edge next_e,
 880                           htab_t rename_map, VEC (tree, heap) **newivs,
 881                           htab_t newivs_index, htab_t bb_pbb_mapping,
 882                           int level, htab_t params_index)
 883 {
 884   struct loop *loop = graphite_create_new_loop (region, next_e, stmt,
 885                                                 context_loop, newivs,
 886                                                 newivs_index, params_index);
 887   edge last_e = single_exit (loop);
 888   edge to_body = single_succ_edge (loop->header);
 889   basic_block after = to_body->dest;
 890
 891   /* Create a basic block for loop close phi nodes.  */
 892   last_e = single_succ_edge (split_edge (last_e));
 893
 894   /* Translate the body of the loop.  */
 895   next_e = translate_clast (region, loop, stmt->body, to_body, rename_map,
 896                             newivs, newivs_index, bb_pbb_mapping, level + 1,
 897                             params_index);
 898   redirect_edge_succ_nodup (next_e, after);
 899   set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
 900
 901    /* Remove from rename_map all the tuples containing variables
 902       defined in loop's body.  */
 903   insert_loop_close_phis (rename_map, loop);
 904
 905   if (flag_loop_parallelize_all
 906       && !dependency_in_loop_p (loop, bb_pbb_mapping,
 907                                 get_scattering_level (level)))
 908     loop->can_be_parallel = true;
 909
 910   return last_e;
 911 }
 912
 913 /* Translates a clast for statement STMT to gimple.  First a guard is created
 914    protecting the loop, if it is executed zero times.  In this guard we create
 915    the real loop structure.
 916
 917    - REGION is the sese region we used to generate the scop.
 918    - NEXT_E is the edge where new generated code should be attached.
 919    - RENAME_MAP contains a set of tuples of new names associated to
 920      the original variables names.
 921    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 922    - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 923      the sese region.  */
 924 static edge
 925 translate_clast_for (sese region, loop_p context_loop, struct clast_for *stmt,
 926                      edge next_e, htab_t rename_map, VEC (tree, heap) **newivs,
 927                      htab_t newivs_index, htab_t bb_pbb_mapping, int level,
 928                      htab_t params_index)
 929 {
 930   edge last_e = graphite_create_new_loop_guard (region, next_e, stmt, *newivs,
 931                                            newivs_index, params_index);
 932
 933   edge true_e = get_true_edge_from_guard_bb (next_e->dest);
 934   edge false_e = get_false_edge_from_guard_bb (next_e->dest);
 935   edge exit_true_e = single_succ_edge (true_e->dest);
 936   edge exit_false_e = single_succ_edge (false_e->dest);
 937
 938   htab_t before_guard = htab_create (10, rename_map_elt_info,
 939                                      eq_rename_map_elts, free);
 940   htab_traverse (rename_map, copy_renames, before_guard);
 941
 942   next_e = translate_clast_for_loop (region, context_loop, stmt, true_e,
 943                                      rename_map, newivs,
 944                                      newivs_index, bb_pbb_mapping, level,
 945                                      params_index);
 946
 947   insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
 948                      before_guard, rename_map);
 949
 950   htab_delete (before_guard);
 951
 952   return last_e;
 953 }
 954
 955 /* Translates a clast guard statement STMT to gimple.
 956
 957    - REGION is the sese region we used to generate the scop.
 958    - NEXT_E is the edge where new generated code should be attached.
 959    - CONTEXT_LOOP is the loop in which the generated code will be placed
 960    - RENAME_MAP contains a set of tuples of new names associated to
 961      the original variables names.
 962    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 963    - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 964      the sese region.  */
 965 static edge
 966 translate_clast_guard (sese region, loop_p context_loop,
 967                        struct clast_guard *stmt, edge next_e,
 968                        htab_t rename_map, VEC (tree, heap) **newivs,
 969                        htab_t newivs_index, htab_t bb_pbb_mapping, int level,
 970                        htab_t params_index)
 971 {
 972   edge last_e = graphite_create_new_guard (region, next_e, stmt, *newivs,
 973                                            newivs_index, params_index);
 974
 975   edge true_e = get_true_edge_from_guard_bb (next_e->dest);
 976   edge false_e = get_false_edge_from_guard_bb (next_e->dest);
 977   edge exit_true_e = single_succ_edge (true_e->dest);
 978   edge exit_false_e = single_succ_edge (false_e->dest);
 979
 980   htab_t before_guard = htab_create (10, rename_map_elt_info,
 981                                      eq_rename_map_elts, free);
 982   htab_traverse (rename_map, copy_renames, before_guard);
 983
 984   next_e = translate_clast (region, context_loop, stmt->then, true_e,
 985                             rename_map, newivs, newivs_index, bb_pbb_mapping,
 986                             level, params_index);
 987
 988   insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
 989                      before_guard, rename_map);
 990
 991   htab_delete (before_guard);
 992
 993   return last_e;
 994 }
 995
 996 /* Translates a CLAST statement STMT to GCC representation in the
 997    context of a SESE.
 998
 999    - NEXT_E is the edge where new generated code should be attached.
1000    - CONTEXT_LOOP is the loop in which the generated code will be placed
1001    - RENAME_MAP contains a set of tuples of new names associated to
1002      the original variables names.
1003    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
1004 static edge
1005 translate_clast (sese region, loop_p context_loop, struct clast_stmt *stmt,
1006                  edge next_e, htab_t rename_map, VEC (tree, heap) **newivs,
1007                  htab_t newivs_index, htab_t bb_pbb_mapping, int level,
1008                  htab_t params_index)
1009 {
1010   if (!stmt)
1011     return next_e;
1012
1013   if (CLAST_STMT_IS_A (stmt, stmt_root))
1014     ; /* Do nothing.  */
1015
1016   else if (CLAST_STMT_IS_A (stmt, stmt_user))
1017     next_e = translate_clast_user (region, (struct clast_user_stmt *) stmt,
1018                                    next_e, rename_map, newivs, newivs_index,
1019                                    bb_pbb_mapping, params_index);
1020
1021   else if (CLAST_STMT_IS_A (stmt, stmt_for))
1022     next_e = translate_clast_for (region, context_loop,
1023                                   (struct clast_for *) stmt, next_e,
1024                                   rename_map, newivs, newivs_index,
1025                                   bb_pbb_mapping, level, params_index);
1026
1027   else if (CLAST_STMT_IS_A (stmt, stmt_guard))
1028     next_e = translate_clast_guard (region, context_loop,
1029                                     (struct clast_guard *) stmt, next_e,
1030                                     rename_map, newivs, newivs_index,
1031                                     bb_pbb_mapping, level, params_index);
1032
1033   else if (CLAST_STMT_IS_A (stmt, stmt_block))
1034     next_e = translate_clast (region, context_loop,
1035                               ((struct clast_block *) stmt)->body,
1036                               next_e, rename_map, newivs, newivs_index,
1037                               bb_pbb_mapping, level, params_index);
1038   else
1039     gcc_unreachable();
1040
1041   recompute_all_dominators ();
1042   graphite_verify ();
1043
1044   return translate_clast (region, context_loop, stmt->next, next_e,
1045                           rename_map, newivs, newivs_index,
1046                           bb_pbb_mapping, level, params_index);
1047 }
1048
1049 /* Returns the first cloog name used in EXPR.  */
1050
1051 static const char *
1052 find_cloog_iv_in_expr (struct clast_expr *expr)
1053 {
1054   struct clast_term *term = (struct clast_term *) expr;
1055   struct clast_reduction *red;
1056   int i;
1057
1058   if (expr->type == expr_term)
1059     return term->var;
1060
1061   if (expr->type != expr_red)
1062     return NULL;
1063
1064   red = (struct clast_reduction *) expr;
1065   for (i = 0; i < red->n; i++)
1066     {
1067       const char *res = find_cloog_iv_in_expr (red->elts[i]);
1068
1069       if (res)
1070         return res;
1071     }
1072
1073   return NULL;
1074 }
1075
1076 /* Build for USER_STMT a map between the CLAST induction variables and
1077    the corresponding GCC old induction variables.  This information is
1078    stored on each GRAPHITE_BB.  */
1079
1080 static void
1081 compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt)
1082 {
1083   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1084   struct clast_stmt *t;
1085   int index = 0;
1086
1087   for (t = user_stmt->substitutions; t; t = t->next, index++)
1088     {
1089       PTR *slot;
1090       struct ivtype_map_elt_s tmp;
1091       struct clast_expr *expr = (struct clast_expr *)
1092         ((struct clast_assignment *)t)->RHS;
1093
1094       /* Create an entry (clast_var, type).  */
1095       tmp.cloog_iv = find_cloog_iv_in_expr (expr);
1096       if (!tmp.cloog_iv)
1097         continue;
1098
1099       slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
1100
1101       if (slot && !*slot)
1102         {
1103           tree oldiv = pbb_to_depth_to_oldiv (pbb, index);
1104           tree type = TREE_TYPE (oldiv);
1105           *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
1106         }
1107     }
1108 }
1109
1110 /* Walk the CLAST tree starting from STMT and build for each
1111    clast_user_stmt a map between the CLAST induction variables and the
1112    corresponding GCC old induction variables.  This information is
1113    stored on each GRAPHITE_BB.  */
1114
1115 static void
1116 compute_cloog_iv_types (struct clast_stmt *stmt)
1117 {
1118   if (!stmt)
1119     return;
1120
1121   if (CLAST_STMT_IS_A (stmt, stmt_root))
1122     goto next;
1123
1124   if (CLAST_STMT_IS_A (stmt, stmt_user))
1125     {
1126       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
1127       poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
1128       gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1129
1130       if (!GBB_CLOOG_IV_TYPES (gbb))
1131         GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
1132                                                 eq_ivtype_map_elts, free);
1133
1134       compute_cloog_iv_types_1 (pbb, (struct clast_user_stmt *) stmt);
1135       goto next;
1136     }
1137
1138   if (CLAST_STMT_IS_A (stmt, stmt_for))
1139     {
1140       struct clast_stmt *s = ((struct clast_for *) stmt)->body;
1141       compute_cloog_iv_types (s);
1142       goto next;
1143     }
1144
1145   if (CLAST_STMT_IS_A (stmt, stmt_guard))
1146     {
1147       struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
1148       compute_cloog_iv_types (s);
1149       goto next;
1150     }
1151
1152   if (CLAST_STMT_IS_A (stmt, stmt_block))
1153     {
1154       struct clast_stmt *s = ((struct clast_block *) stmt)->body;
1155       compute_cloog_iv_types (s);
1156       goto next;
1157     }
1158
1159   gcc_unreachable ();
1160
1161  next:
1162   compute_cloog_iv_types (stmt->next);
1163 }
1164
1165 /* Free the SCATTERING domain list.  */
1166
1167 static void
1168 free_scattering (CloogDomainList *scattering)
1169 {
1170   while (scattering)
1171     {
1172       CloogDomain *dom = cloog_domain (scattering);
1173       CloogDomainList *next = cloog_next_domain (scattering);
1174
1175       cloog_domain_free (dom);
1176       free (scattering);
1177       scattering = next;
1178     }
1179 }
1180
1181 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1182    Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1183    from 0 to scop_nb_loops (scop).  */
1184
1185 static void
1186 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1187 {
1188   sese region = SCOP_REGION (scop);
1189   int i;
1190   int nb_iterators = scop_max_loop_depth (scop);
1191   int nb_scattering = cloog_program_nb_scattdims (prog);
1192   int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1193   char **iterators = XNEWVEC (char *, nb_iterators * 2);
1194   char **scattering = XNEWVEC (char *, nb_scattering);
1195   char **parameters= XNEWVEC (char *, nb_parameters);
1196
1197   cloog_program_set_names (prog, cloog_names_malloc ());
1198
1199   for (i = 0; i < nb_parameters; i++)
1200     {
1201       tree param = VEC_index (tree, SESE_PARAMS(region), i);
1202       const char *name = get_name (param);
1203       int len;
1204
1205       if (!name)
1206         name = "T";
1207
1208       len = strlen (name);
1209       len += 17;
1210       parameters[i] = XNEWVEC (char, len + 1);
1211       snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1212     }
1213
1214   cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1215   cloog_names_set_parameters (cloog_program_names (prog), parameters);
1216
1217   for (i = 0; i < nb_iterators; i++)
1218     {
1219       int len = 4 + 16;
1220       iterators[i] = XNEWVEC (char, len);
1221       snprintf (iterators[i], len, "git_%d", i);
1222     }
1223
1224   cloog_names_set_nb_iterators (cloog_program_names (prog),
1225                                 nb_iterators);
1226   cloog_names_set_iterators (cloog_program_names (prog),
1227                              iterators);
1228
1229   for (i = 0; i < nb_scattering; i++)
1230     {
1231       int len = 5 + 16;
1232       scattering[i] = XNEWVEC (char, len);
1233       snprintf (scattering[i], len, "scat_%d", i);
1234     }
1235
1236   cloog_names_set_nb_scattering (cloog_program_names (prog),
1237                                  nb_scattering);
1238   cloog_names_set_scattering (cloog_program_names (prog),
1239                               scattering);
1240 }
1241
1242 /* Build cloog program for SCoP.  */
1243
1244 static void
1245 build_cloog_prog (scop_p scop, CloogProgram *prog)
1246 {
1247   int i;
1248   int max_nb_loops = scop_max_loop_depth (scop);
1249   poly_bb_p pbb;
1250   CloogLoop *loop_list = NULL;
1251   CloogBlockList *block_list = NULL;
1252   CloogDomainList *scattering = NULL;
1253   int nbs = 2 * max_nb_loops + 1;
1254   int *scaldims;
1255
1256   cloog_program_set_context
1257     (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop)));
1258   nbs = unify_scattering_dimensions (scop);
1259   scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1260   cloog_program_set_nb_scattdims (prog, nbs);
1261   initialize_cloog_names (scop, prog);
1262
1263   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1264     {
1265       CloogStatement *stmt;
1266       CloogBlock *block;
1267
1268       /* Dead code elimination: when the domain of a PBB is empty,
1269          don't generate code for the PBB.  */
1270       if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1271         continue;
1272
1273       /* Build the new statement and its block.  */
1274       stmt = cloog_statement_alloc (pbb_index (pbb));
1275       block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1276       cloog_statement_set_usr (stmt, pbb);
1277
1278       /* Build loop list.  */
1279       {
1280         CloogLoop *new_loop_list = cloog_loop_malloc ();
1281         cloog_loop_set_next (new_loop_list, loop_list);
1282         cloog_loop_set_domain
1283           (new_loop_list,
1284            new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb)));
1285         cloog_loop_set_block (new_loop_list, block);
1286         loop_list = new_loop_list;
1287       }
1288
1289       /* Build block list.  */
1290       {
1291         CloogBlockList *new_block_list = cloog_block_list_malloc ();
1292
1293         cloog_block_list_set_next (new_block_list, block_list);
1294         cloog_block_list_set_block (new_block_list, block);
1295         block_list = new_block_list;
1296       }
1297
1298       /* Build scattering list.  */
1299       {
1300         /* XXX: Replace with cloog_domain_list_alloc(), when available.  */
1301         CloogDomainList *new_scattering
1302           = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
1303         ppl_Polyhedron_t scat;
1304         CloogDomain *dom;
1305
1306         scat = PBB_TRANSFORMED_SCATTERING (pbb);
1307         dom = new_Cloog_Domain_from_ppl_Polyhedron (scat);
1308
1309         cloog_set_next_domain (new_scattering, scattering);
1310         cloog_set_domain (new_scattering, dom);
1311         scattering = new_scattering;
1312       }
1313     }
1314
1315   cloog_program_set_loop (prog, loop_list);
1316   cloog_program_set_blocklist (prog, block_list);
1317
1318   for (i = 0; i < nbs; i++)
1319     scaldims[i] = 0 ;
1320
1321   cloog_program_set_scaldims (prog, scaldims);
1322
1323   /* Extract scalar dimensions to simplify the code generation problem.  */
1324   cloog_program_extract_scalars (prog, scattering);
1325
1326   /* Apply scattering.  */
1327   cloog_program_scatter (prog, scattering);
1328   free_scattering (scattering);
1329
1330   /* Iterators corresponding to scalar dimensions have to be extracted.  */
1331   cloog_names_scalarize (cloog_program_names (prog), nbs,
1332                          cloog_program_scaldims (prog));
1333
1334   /* Free blocklist.  */
1335   {
1336     CloogBlockList *next = cloog_program_blocklist (prog);
1337
1338     while (next)
1339       {
1340         CloogBlockList *toDelete = next;
1341         next = cloog_block_list_next (next);
1342         cloog_block_list_set_next (toDelete, NULL);
1343         cloog_block_list_set_block (toDelete, NULL);
1344         cloog_block_list_free (toDelete);
1345       }
1346     cloog_program_set_blocklist (prog, NULL);
1347   }
1348 }
1349
1350 /* Return the options that will be used in GLOOG.  */
1351
1352 static CloogOptions *
1353 set_cloog_options (void)
1354 {
1355   CloogOptions *options = cloog_options_malloc ();
1356
1357   /* Change cloog output language to C.  If we do use FORTRAN instead, cloog
1358      will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1359      we pass an incomplete program to cloog.  */
1360   options->language = LANGUAGE_C;
1361
1362   /* Enable complex equality spreading: removes dummy statements
1363      (assignments) in the generated code which repeats the
1364      substitution equations for statements.  This is useless for
1365      GLooG.  */
1366   options->esp = 1;
1367
1368   /* Enable C pretty-printing mode: normalizes the substitution
1369      equations for statements.  */
1370   options->cpp = 1;
1371
1372   /* Allow cloog to build strides with a stride width different to one.
1373      This example has stride = 4:
1374
1375      for (i = 0; i < 20; i += 4)
1376        A  */
1377   options->strides = 1;
1378
1379   /* Disable optimizations and make cloog generate source code closer to the
1380      input.  This is useful for debugging,  but later we want the optimized
1381      code.
1382
1383      XXX: We can not disable optimizations, as loop blocking is not working
1384      without them.  */
1385   if (0)
1386     {
1387       options->f = -1;
1388       options->l = INT_MAX;
1389     }
1390
1391   return options;
1392 }
1393
1394 /* Prints STMT to STDERR.  */
1395
1396 void
1397 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1398 {
1399   CloogOptions *options = set_cloog_options ();
1400
1401   pprint (file, stmt, 0, options);
1402   cloog_options_free (options);
1403 }
1404
1405 /* Prints STMT to STDERR.  */
1406
1407 void
1408 debug_clast_stmt (struct clast_stmt *stmt)
1409 {
1410   print_clast_stmt (stderr, stmt);
1411 }
1412
1413 /* Translate SCOP to a CLooG program and clast.  These two
1414    representations should be freed together: a clast cannot be used
1415    without a program.  */
1416
1417 cloog_prog_clast
1418 scop_to_clast (scop_p scop)
1419 {
1420   CloogOptions *options = set_cloog_options ();
1421   cloog_prog_clast pc;
1422
1423   /* Connect new cloog prog generation to graphite.  */
1424   pc.prog = cloog_program_malloc ();
1425   build_cloog_prog (scop, pc.prog);
1426   pc.prog = cloog_program_generate (pc.prog, options);
1427   pc.stmt = cloog_clast_create (pc.prog, options);
1428
1429   cloog_options_free (options);
1430   return pc;
1431 }
1432
1433 /* Prints to FILE the code generated by CLooG for SCOP.  */
1434
1435 void
1436 print_generated_program (FILE *file, scop_p scop)
1437 {
1438   CloogOptions *options = set_cloog_options ();
1439   cloog_prog_clast pc = scop_to_clast (scop);
1440
1441   fprintf (file, "       (prog: \n");
1442   cloog_program_print (file, pc.prog);
1443   fprintf (file, "       )\n");
1444
1445   fprintf (file, "       (clast: \n");
1446   pprint (file, pc.stmt, 0, options);
1447   fprintf (file, "       )\n");
1448
1449   cloog_options_free (options);
1450   cloog_clast_free (pc.stmt);
1451   cloog_program_free (pc.prog);
1452 }
1453
1454 /* Prints to STDERR the code generated by CLooG for SCOP.  */
1455
1456 void
1457 debug_generated_program (scop_p scop)
1458 {
1459   print_generated_program (stderr, scop);
1460 }
1461
1462 /* Add CLooG names to parameter index.  The index is used to translate
1463    back from CLooG names to GCC trees.  */
1464
1465 static void
1466 create_params_index (htab_t index_table, CloogProgram *prog) {
1467   CloogNames* names = cloog_program_names (prog);
1468   int nb_parameters = cloog_names_nb_parameters (names);
1469   char **parameters = cloog_names_parameters (names);
1470   int i;
1471
1472   for (i = 0; i < nb_parameters; i++)
1473     save_clast_name_index (index_table, parameters[i], i);
1474 }
1475
1476 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1477    the given SCOP.  Return true if code generation succeeded.
1478    BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1479 */
1480
1481 bool
1482 gloog (scop_p scop, VEC (scop_p, heap) *scops, htab_t bb_pbb_mapping)
1483 {
1484   VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1485   loop_p context_loop;
1486   sese region = SCOP_REGION (scop);
1487   ifsese if_region = NULL;
1488   htab_t rename_map, newivs_index, params_index;
1489   cloog_prog_clast pc;
1490   int i;
1491
1492   timevar_push (TV_GRAPHITE_CODE_GEN);
1493   gloog_error = false;
1494
1495   pc = scop_to_clast (scop);
1496
1497   if (dump_file && (dump_flags & TDF_DETAILS))
1498     {
1499       fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1500       print_clast_stmt (dump_file, pc.stmt);
1501       fprintf (dump_file, "\n");
1502     }
1503
1504   recompute_all_dominators ();
1505   graphite_verify ();
1506
1507   if_region = move_sese_in_condition (region);
1508   sese_insert_phis_for_liveouts (region,
1509                                  if_region->region->exit->src,
1510                                  if_region->false_region->exit,
1511                                  if_region->true_region->exit);
1512   recompute_all_dominators ();
1513   graphite_verify ();
1514
1515   context_loop = SESE_ENTRY (region)->src->loop_father;
1516   compute_cloog_iv_types (pc.stmt);
1517   rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
1518   newivs_index = htab_create (10, clast_name_index_elt_info,
1519                               eq_clast_name_indexes, free);
1520   params_index = htab_create (10, clast_name_index_elt_info,
1521                               eq_clast_name_indexes, free);
1522
1523   create_params_index (params_index, pc.prog);
1524
1525   translate_clast (region, context_loop, pc.stmt,
1526                    if_region->true_region->entry,
1527                    rename_map, &newivs, newivs_index,
1528                    bb_pbb_mapping, 1, params_index);
1529   graphite_verify ();
1530   sese_adjust_liveout_phis (region, rename_map,
1531                             if_region->region->exit->src,
1532                             if_region->false_region->exit,
1533                             if_region->true_region->exit);
1534   scev_reset_htab ();
1535   rename_nb_iterations (rename_map);
1536
1537   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1538     rename_sese_parameters (rename_map, SCOP_REGION (scop));
1539
1540   recompute_all_dominators ();
1541   graphite_verify ();
1542
1543   if (gloog_error)
1544     set_ifsese_condition (if_region, integer_zero_node);
1545
1546   free (if_region->true_region);
1547   free (if_region->region);
1548   free (if_region);
1549
1550   htab_delete (rename_map);
1551   htab_delete (newivs_index);
1552   htab_delete (params_index);
1553   VEC_free (tree, heap, newivs);
1554   cloog_clast_free (pc.stmt);
1555   cloog_program_free (pc.prog);
1556   timevar_pop (TV_GRAPHITE_CODE_GEN);
1557
1558   if (dump_file && (dump_flags & TDF_DETAILS))
1559     {
1560       loop_p loop;
1561       loop_iterator li;
1562       int num_no_dependency = 0;
1563
1564       FOR_EACH_LOOP (li, loop, 0)
1565         if (loop->can_be_parallel)
1566           num_no_dependency++;
1567
1568       fprintf (dump_file, "\n%d loops carried no dependency.\n",
1569                num_no_dependency);
1570     }
1571
1572   return !gloog_error;
1573 }
1574
1575 #endif