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