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