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