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