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, struct clast_stmt *, edge, htab_t, VEC (tree, heap) **,
 728                  htab_t, htab_t, 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    - RENAME_MAP contains a set of tuples of new names associated to
 735      the original variables names.
 736    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 737    - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 738      the sese region.  */
 739 static edge
 740 translate_clast_user (sese region, struct clast_user_stmt *stmt, edge next_e,
 741                       htab_t rename_map, VEC (tree, heap) **newivs,
 742                       htab_t newivs_index, htab_t bb_pbb_mapping,
 743                       htab_t params_index)
 744 {
 745   poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
 746   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
 747
 748   if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
 749     return next_e;
 750
 751   build_iv_mapping (rename_map, region, *newivs, newivs_index, stmt,
 752                     params_index);
 753   next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region,
 754                                            next_e, rename_map);
 755   mark_bb_with_pbb (pbb, next_e->src, bb_pbb_mapping);
 756   update_ssa (TODO_update_ssa);
 757
 758   return next_e;
 759 }
 760
 761 /* Mark a loop parallel, if the graphite dependency check cannot find any
 762    dependencies.  This triggers parallel code generation in the autopar pass.
 763    */
 764 static void
 765 try_mark_loop_parallel (sese region, loop_p loop, htab_t bb_pbb_mapping)
 766 {
 767   loop_p outermost_loop =  SESE_ENTRY (region)->src->loop_father;
 768   int level = loop_depth (loop) - loop_depth (outermost_loop);
 769
 770   if (flag_loop_parallelize_all
 771       && !dependency_in_loop_p (loop, bb_pbb_mapping,
 772         get_scattering_level (level)))
 773     loop->can_be_parallel = true;
 774 }
 775
 776 static tree gcc_type_for_iv_of_clast_loop (struct clast_for *);
 777
 778
 779 /* Creates a new if region protecting the loop to be executed, if the execution
 780    count is zero (lb > ub).  */
 781 static edge
 782 graphite_create_new_loop_guard (sese region, edge entry_edge,
 783                                 struct clast_for *stmt,
 784                                 VEC (tree, heap) *newivs,
 785                                 htab_t newivs_index, htab_t params_index)
 786 {
 787   tree cond_expr;
 788   edge exit_edge;
 789   tree type = gcc_type_for_iv_of_clast_loop (stmt);
 790   tree lb = clast_to_gcc_expression (type, stmt->LB, region, newivs,
 791                                      newivs_index, params_index);
 792   tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs,
 793                                      newivs_index, params_index);
 794
 795   /* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a
 796      loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this becomes
 797      2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
 798      However lb < ub + 1 is false, as expected.
 799      There might be a problem with cases where ub is 2^32.  */
 800   tree one;
 801   Value gmp_one;
 802   value_init (gmp_one);
 803   value_set_si (gmp_one, 1);
 804   one = gmp_cst_to_tree (type, gmp_one);
 805   value_clear (gmp_one);
 806
 807   ub = fold_build2 (PLUS_EXPR, type, ub, one);
 808   cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub);
 809
 810   exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
 811
 812   return exit_edge;
 813 }
 814
 815
 816 /* Create the loop for a clast for statement.
 817
 818    - REGION is the sese region we used to generate the scop.
 819    - NEXT_E is the edge where new generated code should be attached.
 820    - RENAME_MAP contains a set of tuples of new names associated to
 821      the original variables names.
 822    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 823    - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 824      the sese region.  */
 825 static edge
 826 translate_clast_for_loop (sese region, struct clast_for *stmt, edge next_e,
 827                      htab_t rename_map, VEC (tree, heap) **newivs,
 828                      htab_t newivs_index, htab_t bb_pbb_mapping,
 829                      htab_t params_index)
 830 {
 831   loop_p context_loop = next_e->dest->loop_father;
 832   loop_p loop = graphite_create_new_loop (region, next_e, stmt, context_loop,
 833                                           newivs, newivs_index, params_index);
 834   edge last_e = single_exit (loop);
 835   edge body = single_succ_edge (loop->header);
 836
 837   next_e = translate_clast (region, stmt->body, body, rename_map, newivs,
 838                             newivs_index, bb_pbb_mapping, params_index);
 839
 840   /* Create a basic block for loop close phi nodes.  */
 841   last_e = single_succ_edge (split_edge (last_e));
 842   insert_loop_close_phis (rename_map, loop);
 843
 844   try_mark_loop_parallel (region, loop, bb_pbb_mapping);
 845
 846   return last_e;
 847 }
 848
 849 /* Translates a clast for statement STMT to gimple.  First a guard is created
 850    protecting the loop, if it is executed zero times.  In this guard we create
 851    the real loop structure.
 852
 853    - REGION is the sese region we used to generate the scop.
 854    - NEXT_E is the edge where new generated code should be attached.
 855    - RENAME_MAP contains a set of tuples of new names associated to
 856      the original variables names.
 857    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 858    - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 859      the sese region.  */
 860 static edge
 861 translate_clast_for (sese region, struct clast_for *stmt, edge next_e,
 862                      htab_t rename_map, VEC (tree, heap) **newivs,
 863                      htab_t newivs_index, htab_t bb_pbb_mapping,
 864                      htab_t params_index)
 865 {
 866   edge last_e = graphite_create_new_loop_guard (region, next_e, stmt, *newivs,
 867                                            newivs_index, params_index);
 868
 869   edge true_e = get_true_edge_from_guard_bb (next_e->dest);
 870   edge false_e = get_false_edge_from_guard_bb (next_e->dest);
 871   edge exit_true_e = single_succ_edge (true_e->dest);
 872   edge exit_false_e = single_succ_edge (false_e->dest);
 873
 874   htab_t before_guard = htab_create (10, rename_map_elt_info,
 875                                      eq_rename_map_elts, free);
 876   htab_traverse (rename_map, copy_renames, before_guard);
 877
 878   next_e = translate_clast_for_loop (region, stmt, true_e, rename_map, newivs,
 879                                      newivs_index, bb_pbb_mapping,
 880                                      params_index);
 881
 882   insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
 883                      before_guard, rename_map);
 884
 885   htab_delete (before_guard);
 886
 887   return last_e;
 888 }
 889
 890 /* Translates a clast guard statement STMT to gimple.
 891
 892    - REGION is the sese region we used to generate the scop.
 893    - NEXT_E is the edge where new generated code should be attached.
 894    - RENAME_MAP contains a set of tuples of new names associated to
 895      the original variables names.
 896    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 897    - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
 898      the sese region.  */
 899 static edge
 900 translate_clast_guard (sese region, struct clast_guard *stmt, edge next_e,
 901                        htab_t rename_map, VEC (tree, heap) **newivs,
 902                        htab_t newivs_index, htab_t bb_pbb_mapping,
 903                        htab_t params_index)
 904 {
 905   edge last_e = graphite_create_new_guard (region, next_e, stmt, *newivs,
 906                                            newivs_index, params_index);
 907
 908   edge true_e = get_true_edge_from_guard_bb (next_e->dest);
 909   edge false_e = get_false_edge_from_guard_bb (next_e->dest);
 910   edge exit_true_e = single_succ_edge (true_e->dest);
 911   edge exit_false_e = single_succ_edge (false_e->dest);
 912
 913   htab_t before_guard = htab_create (10, rename_map_elt_info,
 914                                      eq_rename_map_elts, free);
 915   htab_traverse (rename_map, copy_renames, before_guard);
 916
 917   next_e = translate_clast (region, stmt->then, true_e,
 918                             rename_map, newivs, newivs_index, bb_pbb_mapping,
 919                             params_index);
 920
 921   insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
 922                      before_guard, rename_map);
 923
 924   htab_delete (before_guard);
 925
 926   return last_e;
 927 }
 928
 929 /* Translates a CLAST statement STMT to GCC representation in the
 930    context of a SESE.
 931
 932    - NEXT_E is the edge where new generated code should be attached.
 933    - RENAME_MAP contains a set of tuples of new names associated to
 934      the original variables names.
 935    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
 936 static edge
 937 translate_clast (sese region, struct clast_stmt *stmt,
 938                  edge next_e, htab_t rename_map, VEC (tree, heap) **newivs,
 939                  htab_t newivs_index, htab_t bb_pbb_mapping,
 940                  htab_t params_index)
 941 {
 942   if (!stmt)
 943     return next_e;
 944
 945   if (CLAST_STMT_IS_A (stmt, stmt_root))
 946     ; /* Do nothing.  */
 947
 948   else if (CLAST_STMT_IS_A (stmt, stmt_user))
 949     next_e = translate_clast_user (region, (struct clast_user_stmt *) stmt,
 950                                    next_e, rename_map, newivs, newivs_index,
 951                                    bb_pbb_mapping, params_index);
 952
 953   else if (CLAST_STMT_IS_A (stmt, stmt_for))
 954     next_e = translate_clast_for (region,
 955                                   (struct clast_for *) stmt, next_e, rename_map,
 956                                   newivs, newivs_index, bb_pbb_mapping,
 957                                   params_index);
 958
 959   else if (CLAST_STMT_IS_A (stmt, stmt_guard))
 960     next_e = translate_clast_guard (region, (struct clast_guard *) stmt, next_e,
 961                                     rename_map, newivs, newivs_index,
 962                                     bb_pbb_mapping, params_index);
 963
 964   else if (CLAST_STMT_IS_A (stmt, stmt_block))
 965     next_e = translate_clast (region, ((struct clast_block *) stmt)->body,
 966                               next_e, rename_map, newivs, newivs_index,
 967                               bb_pbb_mapping, params_index);
 968   else
 969     gcc_unreachable();
 970
 971   recompute_all_dominators ();
 972   graphite_verify ();
 973
 974   return translate_clast (region, stmt->next, next_e, rename_map, newivs,
 975                           newivs_index, bb_pbb_mapping, params_index);
 976 }
 977
 978 /* Returns the first cloog name used in EXPR.  */
 979
 980 static const char *
 981 find_cloog_iv_in_expr (struct clast_expr *expr)
 982 {
 983   struct clast_term *term = (struct clast_term *) expr;
 984
 985   if (expr->type == expr_term
 986       && !term->var)
 987     return NULL;
 988
 989   if (expr->type == expr_term)
 990     return term->var;
 991
 992   if (expr->type == expr_red)
 993     {
 994       int i;
 995       struct clast_reduction *red = (struct clast_reduction *) expr;
 996
 997       for (i = 0; i < red->n; i++)
 998         {
 999           const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
1000
1001           if (res)
1002             return res;
1003         }
1004     }
1005
1006   return NULL;
1007 }
1008
1009 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
1010    induction variables and the corresponding GCC old induction
1011    variables.  This information is stored on each GRAPHITE_BB.  */
1012
1013 static void
1014 compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt)
1015 {
1016   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1017   struct clast_stmt *t;
1018   int index = 0;
1019
1020   for (t = user_stmt->substitutions; t; t = t->next, index++)
1021     {
1022       PTR *slot;
1023       struct ivtype_map_elt_s tmp;
1024       struct clast_expr *expr = (struct clast_expr *)
1025         ((struct clast_assignment *)t)->RHS;
1026
1027       /* Create an entry (clast_var, type).  */
1028       tmp.cloog_iv = find_cloog_iv_in_expr (expr);
1029       if (!tmp.cloog_iv)
1030         continue;
1031
1032       slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
1033
1034       if (slot && !*slot)
1035         {
1036           tree oldiv = pbb_to_depth_to_oldiv (pbb, index);
1037           tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
1038           *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
1039         }
1040     }
1041 }
1042
1043 /* Walk the CLAST tree starting from STMT and build for each
1044    clast_user_stmt a map between the CLAST induction variables and the
1045    corresponding GCC old induction variables.  This information is
1046    stored on each GRAPHITE_BB.  */
1047
1048 static void
1049 compute_cloog_iv_types (struct clast_stmt *stmt)
1050 {
1051   if (!stmt)
1052     return;
1053
1054   if (CLAST_STMT_IS_A (stmt, stmt_root))
1055     goto next;
1056
1057   if (CLAST_STMT_IS_A (stmt, stmt_user))
1058     {
1059       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
1060       poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
1061       gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1062
1063       if (!GBB_CLOOG_IV_TYPES (gbb))
1064         GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
1065                                                 eq_ivtype_map_elts, free);
1066
1067       compute_cloog_iv_types_1 (pbb, (struct clast_user_stmt *) stmt);
1068       goto next;
1069     }
1070
1071   if (CLAST_STMT_IS_A (stmt, stmt_for))
1072     {
1073       struct clast_stmt *s = ((struct clast_for *) stmt)->body;
1074       compute_cloog_iv_types (s);
1075       goto next;
1076     }
1077
1078   if (CLAST_STMT_IS_A (stmt, stmt_guard))
1079     {
1080       struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
1081       compute_cloog_iv_types (s);
1082       goto next;
1083     }
1084
1085   if (CLAST_STMT_IS_A (stmt, stmt_block))
1086     {
1087       struct clast_stmt *s = ((struct clast_block *) stmt)->body;
1088       compute_cloog_iv_types (s);
1089       goto next;
1090     }
1091
1092   gcc_unreachable ();
1093
1094  next:
1095   compute_cloog_iv_types (stmt->next);
1096 }
1097
1098 /* Free the SCATTERING domain list.  */
1099
1100 static void
1101 free_scattering (CloogDomainList *scattering)
1102 {
1103   while (scattering)
1104     {
1105       CloogDomain *dom = cloog_domain (scattering);
1106       CloogDomainList *next = cloog_next_domain (scattering);
1107
1108       cloog_domain_free (dom);
1109       free (scattering);
1110       scattering = next;
1111     }
1112 }
1113
1114 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1115    Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1116    from 0 to scop_nb_loops (scop).  */
1117
1118 static void
1119 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1120 {
1121   sese region = SCOP_REGION (scop);
1122   int i;
1123   int nb_iterators = scop_max_loop_depth (scop);
1124   int nb_scattering = cloog_program_nb_scattdims (prog);
1125   int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1126   char **iterators = XNEWVEC (char *, nb_iterators * 2);
1127   char **scattering = XNEWVEC (char *, nb_scattering);
1128   char **parameters= XNEWVEC (char *, nb_parameters);
1129
1130   cloog_program_set_names (prog, cloog_names_malloc ());
1131
1132   for (i = 0; i < nb_parameters; i++)
1133     {
1134       tree param = VEC_index (tree, SESE_PARAMS(region), i);
1135       const char *name = get_name (param);
1136       int len;
1137
1138       if (!name)
1139         name = "T";
1140
1141       len = strlen (name);
1142       len += 17;
1143       parameters[i] = XNEWVEC (char, len + 1);
1144       snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1145     }
1146
1147   cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1148   cloog_names_set_parameters (cloog_program_names (prog), parameters);
1149
1150   for (i = 0; i < nb_iterators; i++)
1151     {
1152       int len = 4 + 16;
1153       iterators[i] = XNEWVEC (char, len);
1154       snprintf (iterators[i], len, "git_%d", i);
1155     }
1156
1157   cloog_names_set_nb_iterators (cloog_program_names (prog),
1158                                 nb_iterators);
1159   cloog_names_set_iterators (cloog_program_names (prog),
1160                              iterators);
1161
1162   for (i = 0; i < nb_scattering; i++)
1163     {
1164       int len = 5 + 16;
1165       scattering[i] = XNEWVEC (char, len);
1166       snprintf (scattering[i], len, "scat_%d", i);
1167     }
1168
1169   cloog_names_set_nb_scattering (cloog_program_names (prog),
1170                                  nb_scattering);
1171   cloog_names_set_scattering (cloog_program_names (prog),
1172                               scattering);
1173 }
1174
1175 /* Build cloog program for SCoP.  */
1176
1177 static void
1178 build_cloog_prog (scop_p scop, CloogProgram *prog)
1179 {
1180   int i;
1181   int max_nb_loops = scop_max_loop_depth (scop);
1182   poly_bb_p pbb;
1183   CloogLoop *loop_list = NULL;
1184   CloogBlockList *block_list = NULL;
1185   CloogDomainList *scattering = NULL;
1186   int nbs = 2 * max_nb_loops + 1;
1187   int *scaldims;
1188
1189   cloog_program_set_context
1190     (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop)));
1191   nbs = unify_scattering_dimensions (scop);
1192   scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1193   cloog_program_set_nb_scattdims (prog, nbs);
1194   initialize_cloog_names (scop, prog);
1195
1196   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1197     {
1198       CloogStatement *stmt;
1199       CloogBlock *block;
1200
1201       /* Dead code elimination: when the domain of a PBB is empty,
1202          don't generate code for the PBB.  */
1203       if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1204         continue;
1205
1206       /* Build the new statement and its block.  */
1207       stmt = cloog_statement_alloc (pbb_index (pbb));
1208       block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1209       cloog_statement_set_usr (stmt, pbb);
1210
1211       /* Build loop list.  */
1212       {
1213         CloogLoop *new_loop_list = cloog_loop_malloc ();
1214         cloog_loop_set_next (new_loop_list, loop_list);
1215         cloog_loop_set_domain
1216           (new_loop_list,
1217            new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb)));
1218         cloog_loop_set_block (new_loop_list, block);
1219         loop_list = new_loop_list;
1220       }
1221
1222       /* Build block list.  */
1223       {
1224         CloogBlockList *new_block_list = cloog_block_list_malloc ();
1225
1226         cloog_block_list_set_next (new_block_list, block_list);
1227         cloog_block_list_set_block (new_block_list, block);
1228         block_list = new_block_list;
1229       }
1230
1231       /* Build scattering list.  */
1232       {
1233         /* XXX: Replace with cloog_domain_list_alloc(), when available.  */
1234         CloogDomainList *new_scattering
1235           = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
1236         ppl_Polyhedron_t scat;
1237         CloogDomain *dom;
1238
1239         scat = PBB_TRANSFORMED_SCATTERING (pbb);
1240         dom = new_Cloog_Domain_from_ppl_Polyhedron (scat);
1241
1242         cloog_set_next_domain (new_scattering, scattering);
1243         cloog_set_domain (new_scattering, dom);
1244         scattering = new_scattering;
1245       }
1246     }
1247
1248   cloog_program_set_loop (prog, loop_list);
1249   cloog_program_set_blocklist (prog, block_list);
1250
1251   for (i = 0; i < nbs; i++)
1252     scaldims[i] = 0 ;
1253
1254   cloog_program_set_scaldims (prog, scaldims);
1255
1256   /* Extract scalar dimensions to simplify the code generation problem.  */
1257   cloog_program_extract_scalars (prog, scattering);
1258
1259   /* Apply scattering.  */
1260   cloog_program_scatter (prog, scattering);
1261   free_scattering (scattering);
1262
1263   /* Iterators corresponding to scalar dimensions have to be extracted.  */
1264   cloog_names_scalarize (cloog_program_names (prog), nbs,
1265                          cloog_program_scaldims (prog));
1266
1267   /* Free blocklist.  */
1268   {
1269     CloogBlockList *next = cloog_program_blocklist (prog);
1270
1271     while (next)
1272       {
1273         CloogBlockList *toDelete = next;
1274         next = cloog_block_list_next (next);
1275         cloog_block_list_set_next (toDelete, NULL);
1276         cloog_block_list_set_block (toDelete, NULL);
1277         cloog_block_list_free (toDelete);
1278       }
1279     cloog_program_set_blocklist (prog, NULL);
1280   }
1281 }
1282
1283 /* Return the options that will be used in GLOOG.  */
1284
1285 static CloogOptions *
1286 set_cloog_options (void)
1287 {
1288   CloogOptions *options = cloog_options_malloc ();
1289
1290   /* Change cloog output language to C.  If we do use FORTRAN instead, cloog
1291      will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1292      we pass an incomplete program to cloog.  */
1293   options->language = LANGUAGE_C;
1294
1295   /* Enable complex equality spreading: removes dummy statements
1296      (assignments) in the generated code which repeats the
1297      substitution equations for statements.  This is useless for
1298      GLooG.  */
1299   options->esp = 1;
1300
1301   /* Enable C pretty-printing mode: normalizes the substitution
1302      equations for statements.  */
1303   options->cpp = 1;
1304
1305   /* Allow cloog to build strides with a stride width different to one.
1306      This example has stride = 4:
1307
1308      for (i = 0; i < 20; i += 4)
1309        A  */
1310   options->strides = 1;
1311
1312   /* Disable optimizations and make cloog generate source code closer to the
1313      input.  This is useful for debugging,  but later we want the optimized
1314      code.
1315
1316      XXX: We can not disable optimizations, as loop blocking is not working
1317      without them.  */
1318   if (0)
1319     {
1320       options->f = -1;
1321       options->l = INT_MAX;
1322     }
1323
1324   return options;
1325 }
1326
1327 /* Prints STMT to STDERR.  */
1328
1329 void
1330 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1331 {
1332   CloogOptions *options = set_cloog_options ();
1333
1334   pprint (file, stmt, 0, options);
1335   cloog_options_free (options);
1336 }
1337
1338 /* Prints STMT to STDERR.  */
1339
1340 void
1341 debug_clast_stmt (struct clast_stmt *stmt)
1342 {
1343   print_clast_stmt (stderr, stmt);
1344 }
1345
1346 /* Translate SCOP to a CLooG program and clast.  These two
1347    representations should be freed together: a clast cannot be used
1348    without a program.  */
1349
1350 cloog_prog_clast
1351 scop_to_clast (scop_p scop)
1352 {
1353   CloogOptions *options = set_cloog_options ();
1354   cloog_prog_clast pc;
1355
1356   /* Connect new cloog prog generation to graphite.  */
1357   pc.prog = cloog_program_malloc ();
1358   build_cloog_prog (scop, pc.prog);
1359   pc.prog = cloog_program_generate (pc.prog, options);
1360   pc.stmt = cloog_clast_create (pc.prog, options);
1361
1362   cloog_options_free (options);
1363   return pc;
1364 }
1365
1366 /* Prints to FILE the code generated by CLooG for SCOP.  */
1367
1368 void
1369 print_generated_program (FILE *file, scop_p scop)
1370 {
1371   CloogOptions *options = set_cloog_options ();
1372   cloog_prog_clast pc = scop_to_clast (scop);
1373
1374   fprintf (file, "       (prog: \n");
1375   cloog_program_print (file, pc.prog);
1376   fprintf (file, "       )\n");
1377
1378   fprintf (file, "       (clast: \n");
1379   pprint (file, pc.stmt, 0, options);
1380   fprintf (file, "       )\n");
1381
1382   cloog_options_free (options);
1383   cloog_clast_free (pc.stmt);
1384   cloog_program_free (pc.prog);
1385 }
1386
1387 /* Prints to STDERR the code generated by CLooG for SCOP.  */
1388
1389 void
1390 debug_generated_program (scop_p scop)
1391 {
1392   print_generated_program (stderr, scop);
1393 }
1394
1395 /* Add CLooG names to parameter index.  The index is used to translate back from
1396  * CLooG names to GCC trees.  */
1397
1398 static void
1399 create_params_index (htab_t index_table, CloogProgram *prog) {
1400   CloogNames* names = cloog_program_names (prog);
1401   int nb_parameters = cloog_names_nb_parameters (names);
1402   char **parameters = cloog_names_parameters (names);
1403   int i;
1404
1405   for (i = 0; i < nb_parameters; i++)
1406     save_clast_name_index (index_table, parameters[i], i);
1407 }
1408
1409 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1410    the given SCOP.  Return true if code generation succeeded.
1411    BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1412 */
1413
1414 bool
1415 gloog (scop_p scop, htab_t bb_pbb_mapping)
1416 {
1417   edge new_scop_exit_edge = NULL;
1418   VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1419   sese region = SCOP_REGION (scop);
1420   ifsese if_region = NULL;
1421   htab_t rename_map, newivs_index, params_index;
1422   cloog_prog_clast pc;
1423
1424   timevar_push (TV_GRAPHITE_CODE_GEN);
1425
1426   pc = scop_to_clast (scop);
1427
1428   if (dump_file && (dump_flags & TDF_DETAILS))
1429     {
1430       fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1431       print_clast_stmt (dump_file, pc.stmt);
1432       fprintf (dump_file, "\n");
1433     }
1434
1435   recompute_all_dominators ();
1436   graphite_verify ();
1437
1438   if_region = move_sese_in_condition (region);
1439   sese_insert_phis_for_liveouts (region,
1440                                  if_region->region->exit->src,
1441                                  if_region->false_region->exit,
1442                                  if_region->true_region->exit);
1443   recompute_all_dominators ();
1444   graphite_verify ();
1445
1446   compute_cloog_iv_types (pc.stmt);
1447   rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
1448   newivs_index = htab_create (10, clast_name_index_elt_info,
1449                               eq_clast_name_indexes, free);
1450   params_index = htab_create (10, clast_name_index_elt_info,
1451                               eq_clast_name_indexes, free);
1452
1453   create_params_index (params_index, pc.prog);
1454
1455   new_scop_exit_edge = translate_clast (region, pc.stmt,
1456                                         if_region->true_region->entry,
1457                                         rename_map, &newivs, newivs_index,
1458                                         bb_pbb_mapping, params_index);
1459   graphite_verify ();
1460   sese_adjust_liveout_phis (region, rename_map,
1461                             if_region->region->exit->src,
1462                             if_region->false_region->exit,
1463                             if_region->true_region->exit);
1464   recompute_all_dominators ();
1465   graphite_verify ();
1466
1467   free (if_region->true_region);
1468   free (if_region->region);
1469   free (if_region);
1470
1471   htab_delete (rename_map);
1472   htab_delete (newivs_index);
1473   htab_delete (params_index);
1474   VEC_free (tree, heap, newivs);
1475   cloog_clast_free (pc.stmt);
1476   cloog_program_free (pc.prog);
1477   timevar_pop (TV_GRAPHITE_CODE_GEN);
1478
1479   if (dump_file && (dump_flags & TDF_DETAILS))
1480     {
1481       loop_p loop;
1482       loop_iterator li;
1483       int num_no_dependency = 0;
1484
1485       FOR_EACH_LOOP (li, loop, 0)
1486         if (loop->can_be_parallel)
1487           num_no_dependency++;
1488
1489       fprintf (dump_file, "\n%d loops carried no dependency.\n",
1490                num_no_dependency);
1491     }
1492
1493   return true;
1494 }
1495
1496 #endif