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