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