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