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 (tree) loop->aux;
  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 /* Returns the scattering dimension for STMTFOR.
 562
 563    FIXME: This is a hackish solution to locate the scattering
 564    dimension in newly created loops. Here the hackish solush
 565    assume that the stmt_for->iterator is always something like:
 566    scat_1 , scat_3 etc., where after "scat_" is loop level in
 567    scattering dimension.
 568 */
 569
 570 static int get_stmtfor_depth (struct clast_for *stmtfor)
 571 {
 572   const char * iterator = stmtfor->iterator;
 573   const char * depth;
 574
 575   depth = strchr (iterator, '_');
 576   if (!strncmp (iterator, "scat_", 5))
 577     return atoi (depth+1);
 578
 579   gcc_unreachable();
 580 }
 581
 582 /* Translates a CLAST statement STMT to GCC representation in the
 583    context of a SESE.
 584
 585    - NEXT_E is the edge where new generated code should be attached.
 586    - CONTEXT_LOOP is the loop in which the generated code will be placed
 587    - RENAME_MAP contains a set of tuples of new names associated to
 588      the original variables names.
 589    - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
 590 */
 591
 592 static edge
 593 translate_clast (sese region, struct loop *context_loop,
 594                  struct clast_stmt *stmt, edge next_e,
 595                  htab_t rename_map, VEC (tree, heap) **newivs,
 596                  htab_t newivs_index, htab_t bb_pbb_mapping)
 597 {
 598   if (!stmt)
 599     return next_e;
 600
 601   if (CLAST_STMT_IS_A (stmt, stmt_root))
 602     return translate_clast (region, context_loop, stmt->next, next_e,
 603                             rename_map, newivs, newivs_index, bb_pbb_mapping);
 604
 605   if (CLAST_STMT_IS_A (stmt, stmt_user))
 606     {
 607       gimple_bb_p gbb;
 608       basic_block new_bb;
 609       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
 610       poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
 611       gbb = PBB_BLACK_BOX (pbb);
 612
 613       if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
 614         return next_e;
 615
 616       build_iv_mapping (rename_map, region, *newivs, newivs_index,
 617                         (struct clast_user_stmt *) stmt);
 618       next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region,
 619                                                next_e, rename_map);
 620       new_bb = next_e->src;
 621       mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
 622       recompute_all_dominators ();
 623       update_ssa (TODO_update_ssa);
 624       graphite_verify ();
 625       return translate_clast (region, context_loop, stmt->next, next_e,
 626                               rename_map, newivs, newivs_index,
 627                               bb_pbb_mapping);
 628     }
 629
 630   if (CLAST_STMT_IS_A (stmt, stmt_for))
 631     {
 632       struct clast_for *stmtfor = (struct clast_for *)stmt;
 633       struct loop *loop
 634         = graphite_create_new_loop (region, next_e, stmtfor,
 635                                     context_loop, newivs, newivs_index);
 636       edge last_e = single_exit (loop);
 637       edge to_body = single_succ_edge (loop->header);
 638       basic_block after = to_body->dest;
 639
 640       loop->aux = XNEW (int);
 641       /* Pass scattering level information of the new loop by LOOP->AUX.  */
 642       *((int *)(loop->aux)) = get_stmtfor_depth (stmtfor);
 643
 644       /* Create a basic block for loop close phi nodes.  */
 645       last_e = single_succ_edge (split_edge (last_e));
 646
 647       /* Translate the body of the loop.  */
 648       next_e = translate_clast
 649         (region, loop, ((struct clast_for *) stmt)->body,
 650          single_succ_edge (loop->header), rename_map, newivs,
 651          newivs_index, bb_pbb_mapping);
 652       redirect_edge_succ_nodup (next_e, after);
 653       set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
 654
 655       /* Remove from rename_map all the tuples containing variables
 656          defined in loop's body.  */
 657       insert_loop_close_phis (rename_map, loop);
 658
 659       recompute_all_dominators ();
 660       graphite_verify ();
 661       return translate_clast (region, context_loop, stmt->next, last_e,
 662                               rename_map, newivs, newivs_index,
 663                               bb_pbb_mapping);
 664     }
 665
 666   if (CLAST_STMT_IS_A (stmt, stmt_guard))
 667     {
 668       edge last_e = graphite_create_new_guard (region, next_e,
 669                                                ((struct clast_guard *) stmt),
 670                                                *newivs, newivs_index);
 671       edge true_e = get_true_edge_from_guard_bb (next_e->dest);
 672       edge false_e = get_false_edge_from_guard_bb (next_e->dest);
 673       edge exit_true_e = single_succ_edge (true_e->dest);
 674       edge exit_false_e = single_succ_edge (false_e->dest);
 675       htab_t before_guard = htab_create (10, rename_map_elt_info,
 676                                          eq_rename_map_elts, free);
 677
 678       htab_traverse (rename_map, copy_renames, before_guard);
 679       next_e = translate_clast (region, context_loop,
 680                                 ((struct clast_guard *) stmt)->then,
 681                                 true_e, rename_map, newivs, newivs_index,
 682                                 bb_pbb_mapping);
 683       insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
 684                          before_guard, rename_map);
 685
 686       htab_delete (before_guard);
 687       recompute_all_dominators ();
 688       graphite_verify ();
 689
 690       return translate_clast (region, context_loop, stmt->next, last_e,
 691                               rename_map, newivs, newivs_index,
 692                               bb_pbb_mapping);
 693     }
 694
 695   if (CLAST_STMT_IS_A (stmt, stmt_block))
 696     {
 697       next_e = translate_clast (region, context_loop,
 698                                 ((struct clast_block *) stmt)->body,
 699                                 next_e, rename_map, newivs, newivs_index,
 700                                 bb_pbb_mapping);
 701       recompute_all_dominators ();
 702       graphite_verify ();
 703       return translate_clast (region, context_loop, stmt->next, next_e,
 704                               rename_map, newivs, newivs_index,
 705                               bb_pbb_mapping);
 706     }
 707
 708   gcc_unreachable ();
 709 }
 710
 711 /* Returns the first cloog name used in EXPR.  */
 712
 713 static const char *
 714 find_cloog_iv_in_expr (struct clast_expr *expr)
 715 {
 716   struct clast_term *term = (struct clast_term *) expr;
 717
 718   if (expr->type == expr_term
 719       && !term->var)
 720     return NULL;
 721
 722   if (expr->type == expr_term)
 723     return term->var;
 724
 725   if (expr->type == expr_red)
 726     {
 727       int i;
 728       struct clast_reduction *red = (struct clast_reduction *) expr;
 729
 730       for (i = 0; i < red->n; i++)
 731         {
 732           const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
 733
 734           if (res)
 735             return res;
 736         }
 737     }
 738
 739   return NULL;
 740 }
 741
 742 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
 743    induction variables and the corresponding GCC old induction
 744    variables.  This information is stored on each GRAPHITE_BB.  */
 745
 746 static void
 747 compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt)
 748 {
 749   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
 750   struct clast_stmt *t;
 751   int index = 0;
 752
 753   for (t = user_stmt->substitutions; t; t = t->next, index++)
 754     {
 755       PTR *slot;
 756       struct ivtype_map_elt_s tmp;
 757       struct clast_expr *expr = (struct clast_expr *)
 758         ((struct clast_assignment *)t)->RHS;
 759
 760       /* Create an entry (clast_var, type).  */
 761       tmp.cloog_iv = find_cloog_iv_in_expr (expr);
 762       if (!tmp.cloog_iv)
 763         continue;
 764
 765       slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
 766
 767       if (!*slot)
 768         {
 769           tree oldiv = pbb_to_depth_to_oldiv (pbb, index);
 770           tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
 771           *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
 772         }
 773     }
 774 }
 775
 776 /* Walk the CLAST tree starting from STMT and build for each
 777    clast_user_stmt a map between the CLAST induction variables and the
 778    corresponding GCC old induction variables.  This information is
 779    stored on each GRAPHITE_BB.  */
 780
 781 static void
 782 compute_cloog_iv_types (struct clast_stmt *stmt)
 783 {
 784   if (!stmt)
 785     return;
 786
 787   if (CLAST_STMT_IS_A (stmt, stmt_root))
 788     goto next;
 789
 790   if (CLAST_STMT_IS_A (stmt, stmt_user))
 791     {
 792       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
 793       poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
 794       gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
 795
 796       if (!GBB_CLOOG_IV_TYPES (gbb))
 797         GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
 798                                                 eq_ivtype_map_elts, free);
 799
 800       compute_cloog_iv_types_1 (pbb, (struct clast_user_stmt *) stmt);
 801       goto next;
 802     }
 803
 804   if (CLAST_STMT_IS_A (stmt, stmt_for))
 805     {
 806       struct clast_stmt *s = ((struct clast_for *) stmt)->body;
 807       compute_cloog_iv_types (s);
 808       goto next;
 809     }
 810
 811   if (CLAST_STMT_IS_A (stmt, stmt_guard))
 812     {
 813       struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
 814       compute_cloog_iv_types (s);
 815       goto next;
 816     }
 817
 818   if (CLAST_STMT_IS_A (stmt, stmt_block))
 819     {
 820       struct clast_stmt *s = ((struct clast_block *) stmt)->body;
 821       compute_cloog_iv_types (s);
 822       goto next;
 823     }
 824
 825   gcc_unreachable ();
 826
 827  next:
 828   compute_cloog_iv_types (stmt->next);
 829 }
 830
 831 /* Free the SCATTERING domain list.  */
 832
 833 static void
 834 free_scattering (CloogDomainList *scattering)
 835 {
 836   while (scattering)
 837     {
 838       CloogDomain *dom = cloog_domain (scattering);
 839       CloogDomainList *next = cloog_next_domain (scattering);
 840
 841       cloog_domain_free (dom);
 842       free (scattering);
 843       scattering = next;
 844     }
 845 }
 846
 847 /* Initialize Cloog's parameter names from the names used in GIMPLE.
 848    Initialize Cloog's iterator names, using 'graphite_iterator_%d'
 849    from 0 to scop_nb_loops (scop).  */
 850
 851 static void
 852 initialize_cloog_names (scop_p scop, CloogProgram *prog)
 853 {
 854   sese region = SCOP_REGION (scop);
 855   int i;
 856   int nb_iterators = scop_max_loop_depth (scop);
 857   int nb_scattering = cloog_program_nb_scattdims (prog);
 858   char **iterators = XNEWVEC (char *, nb_iterators * 2);
 859   char **scattering = XNEWVEC (char *, nb_scattering);
 860
 861   cloog_program_set_names (prog, cloog_names_malloc ());
 862   cloog_names_set_nb_parameters (cloog_program_names (prog),
 863                                  VEC_length (tree, SESE_PARAMS (region)));
 864   cloog_names_set_parameters (cloog_program_names (prog),
 865                               SESE_PARAMS_NAMES (region));
 866
 867   for (i = 0; i < nb_iterators; i++)
 868     {
 869       int len = 4 + 16;
 870       iterators[i] = XNEWVEC (char, len);
 871       snprintf (iterators[i], len, "git_%d", i);
 872     }
 873
 874   cloog_names_set_nb_iterators (cloog_program_names (prog),
 875                                 nb_iterators);
 876   cloog_names_set_iterators (cloog_program_names (prog),
 877                              iterators);
 878
 879   for (i = 0; i < nb_scattering; i++)
 880     {
 881       int len = 5 + 16;
 882       scattering[i] = XNEWVEC (char, len);
 883       snprintf (scattering[i], len, "scat_%d", i);
 884     }
 885
 886   cloog_names_set_nb_scattering (cloog_program_names (prog),
 887                                  nb_scattering);
 888   cloog_names_set_scattering (cloog_program_names (prog),
 889                               scattering);
 890 }
 891
 892 /* Build cloog program for SCoP.  */
 893
 894 static void
 895 build_cloog_prog (scop_p scop, CloogProgram *prog)
 896 {
 897   int i;
 898   int max_nb_loops = scop_max_loop_depth (scop);
 899   poly_bb_p pbb;
 900   CloogLoop *loop_list = NULL;
 901   CloogBlockList *block_list = NULL;
 902   CloogDomainList *scattering = NULL;
 903   int nbs = 2 * max_nb_loops + 1;
 904   int *scaldims;
 905
 906   cloog_program_set_context
 907     (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop)));
 908   nbs = unify_scattering_dimensions (scop);
 909   scaldims = (int *) xmalloc (nbs * (sizeof (int)));
 910   cloog_program_set_nb_scattdims (prog, nbs);
 911   initialize_cloog_names (scop, prog);
 912
 913   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
 914     {
 915       CloogStatement *stmt;
 916       CloogBlock *block;
 917
 918       /* Dead code elimination: when the domain of a PBB is empty,
 919          don't generate code for the PBB.  */
 920       if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
 921         continue;
 922
 923       /* Build the new statement and its block.  */
 924       stmt = cloog_statement_alloc (GBB_BB (PBB_BLACK_BOX (pbb))->index);
 925       block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
 926       cloog_statement_set_usr (stmt, pbb);
 927
 928       /* Build loop list.  */
 929       {
 930         CloogLoop *new_loop_list = cloog_loop_malloc ();
 931         cloog_loop_set_next (new_loop_list, loop_list);
 932         cloog_loop_set_domain
 933           (new_loop_list,
 934            new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb)));
 935         cloog_loop_set_block (new_loop_list, block);
 936         loop_list = new_loop_list;
 937       }
 938
 939       /* Build block list.  */
 940       {
 941         CloogBlockList *new_block_list = cloog_block_list_malloc ();
 942
 943         cloog_block_list_set_next (new_block_list, block_list);
 944         cloog_block_list_set_block (new_block_list, block);
 945         block_list = new_block_list;
 946       }
 947
 948       /* Build scattering list.  */
 949       {
 950         /* XXX: Replace with cloog_domain_list_alloc(), when available.  */
 951         CloogDomainList *new_scattering
 952           = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
 953         ppl_Polyhedron_t scat;
 954         CloogDomain *dom;
 955
 956         scat = PBB_TRANSFORMED_SCATTERING (pbb);
 957         dom = new_Cloog_Domain_from_ppl_Polyhedron (scat);
 958
 959         cloog_set_next_domain (new_scattering, scattering);
 960         cloog_set_domain (new_scattering, dom);
 961         scattering = new_scattering;
 962       }
 963     }
 964
 965   cloog_program_set_loop (prog, loop_list);
 966   cloog_program_set_blocklist (prog, block_list);
 967
 968   for (i = 0; i < nbs; i++)
 969     scaldims[i] = 0 ;
 970
 971   cloog_program_set_scaldims (prog, scaldims);
 972
 973   /* Extract scalar dimensions to simplify the code generation problem.  */
 974   cloog_program_extract_scalars (prog, scattering);
 975
 976   /* Apply scattering.  */
 977   cloog_program_scatter (prog, scattering);
 978   free_scattering (scattering);
 979
 980   /* Iterators corresponding to scalar dimensions have to be extracted.  */
 981   cloog_names_scalarize (cloog_program_names (prog), nbs,
 982                          cloog_program_scaldims (prog));
 983
 984   /* Free blocklist.  */
 985   {
 986     CloogBlockList *next = cloog_program_blocklist (prog);
 987
 988     while (next)
 989       {
 990         CloogBlockList *toDelete = next;
 991         next = cloog_block_list_next (next);
 992         cloog_block_list_set_next (toDelete, NULL);
 993         cloog_block_list_set_block (toDelete, NULL);
 994         cloog_block_list_free (toDelete);
 995       }
 996     cloog_program_set_blocklist (prog, NULL);
 997   }
 998 }
 999
1000 /* Return the options that will be used in GLOOG.  */
1001
1002 static CloogOptions *
1003 set_cloog_options (void)
1004 {
1005   CloogOptions *options = cloog_options_malloc ();
1006
1007   /* Change cloog output language to C.  If we do use FORTRAN instead, cloog
1008      will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1009      we pass an incomplete program to cloog.  */
1010   options->language = LANGUAGE_C;
1011
1012   /* Enable complex equality spreading: removes dummy statements
1013      (assignments) in the generated code which repeats the
1014      substitution equations for statements.  This is useless for
1015      GLooG.  */
1016   options->esp = 1;
1017
1018   /* Enable C pretty-printing mode: normalizes the substitution
1019      equations for statements.  */
1020   options->cpp = 1;
1021
1022   /* Allow cloog to build strides with a stride width different to one.
1023      This example has stride = 4:
1024
1025      for (i = 0; i < 20; i += 4)
1026        A  */
1027   options->strides = 1;
1028
1029   /* Disable optimizations and make cloog generate source code closer to the
1030      input.  This is useful for debugging,  but later we want the optimized
1031      code.
1032
1033      XXX: We can not disable optimizations, as loop blocking is not working
1034      without them.  */
1035   if (0)
1036     {
1037       options->f = -1;
1038       options->l = INT_MAX;
1039     }
1040
1041   return options;
1042 }
1043
1044 /* Prints STMT to STDERR.  */
1045
1046 void
1047 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1048 {
1049   CloogOptions *options = set_cloog_options ();
1050
1051   pprint (file, stmt, 0, options);
1052   cloog_options_free (options);
1053 }
1054
1055 /* Prints STMT to STDERR.  */
1056
1057 void
1058 debug_clast_stmt (struct clast_stmt *stmt)
1059 {
1060   print_clast_stmt (stderr, stmt);
1061 }
1062
1063 /* Translate SCOP to a CLooG program and clast.  These two
1064    representations should be freed together: a clast cannot be used
1065    without a program.  */
1066
1067 cloog_prog_clast
1068 scop_to_clast (scop_p scop)
1069 {
1070   CloogOptions *options = set_cloog_options ();
1071   cloog_prog_clast pc;
1072
1073   /* Connect new cloog prog generation to graphite.  */
1074   pc.prog = cloog_program_malloc ();
1075   build_cloog_prog (scop, pc.prog);
1076   pc.prog = cloog_program_generate (pc.prog, options);
1077   pc.stmt = cloog_clast_create (pc.prog, options);
1078
1079   cloog_options_free (options);
1080   return pc;
1081 }
1082
1083 /* Prints to FILE the code generated by CLooG for SCOP.  */
1084
1085 void
1086 print_generated_program (FILE *file, scop_p scop)
1087 {
1088   CloogOptions *options = set_cloog_options ();
1089   cloog_prog_clast pc = scop_to_clast (scop);
1090
1091   fprintf (file, "       (prog: \n");
1092   cloog_program_print (file, pc.prog);
1093   fprintf (file, "       )\n");
1094
1095   fprintf (file, "       (clast: \n");
1096   pprint (file, pc.stmt, 0, options);
1097   fprintf (file, "       )\n");
1098
1099   cloog_options_free (options);
1100   cloog_clast_free (pc.stmt);
1101   cloog_program_free (pc.prog);
1102 }
1103
1104 /* Prints to STDERR the code generated by CLooG for SCOP.  */
1105
1106 void
1107 debug_generated_program (scop_p scop)
1108 {
1109   print_generated_program (stderr, scop);
1110 }
1111
1112 /* A LOOP is in normal form for Graphite when it contains only one
1113    scalar phi node that defines the main induction variable of the
1114    loop, only one increment of the IV, and only one exit condition.  */
1115
1116 static void
1117 graphite_loop_normal_form (loop_p loop)
1118 {
1119   struct tree_niter_desc niter;
1120   tree nit;
1121   gimple_seq stmts;
1122   edge exit = single_dom_exit (loop);
1123
1124   bool known_niter = number_of_iterations_exit (loop, exit, &niter, false);
1125
1126   /* At this point we should know the number of iterations,  */
1127   gcc_assert (known_niter);
1128
1129   nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
1130                               NULL_TREE);
1131   if (stmts)
1132     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1133
1134   loop->aux = canonicalize_loop_ivs (loop, &nit);
1135 }
1136
1137 /* Converts REGION to loop normal form: one induction variable per loop.  */
1138
1139 static void
1140 build_graphite_loop_normal_form (sese region)
1141 {
1142   int i;
1143   loop_p loop;
1144
1145   for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1146     graphite_loop_normal_form (loop);
1147 }
1148
1149 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1150    the given SCOP.  Return true if code generation succeeded.
1151    BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1152 */
1153
1154 bool
1155 gloog (scop_p scop, htab_t bb_pbb_mapping)
1156 {
1157   edge new_scop_exit_edge = NULL;
1158   VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1159   loop_p context_loop;
1160   sese region = SCOP_REGION (scop);
1161   ifsese if_region = NULL;
1162   htab_t rename_map, newivs_index;
1163   cloog_prog_clast pc;
1164
1165   timevar_push (TV_GRAPHITE_CODE_GEN);
1166
1167   pc = scop_to_clast (scop);
1168
1169   if (dump_file && (dump_flags & TDF_DETAILS))
1170     {
1171       fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1172       print_clast_stmt (dump_file, pc.stmt);
1173       fprintf (dump_file, "\n");
1174     }
1175
1176   build_graphite_loop_normal_form (region);
1177   recompute_all_dominators ();
1178   graphite_verify ();
1179
1180   if_region = move_sese_in_condition (region);
1181   sese_insert_phis_for_liveouts (region,
1182                                  if_region->region->exit->src,
1183                                  if_region->false_region->exit,
1184                                  if_region->true_region->exit);
1185
1186   recompute_all_dominators ();
1187   graphite_verify ();
1188   context_loop = SESE_ENTRY (region)->src->loop_father;
1189   compute_cloog_iv_types (pc.stmt);
1190
1191   rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
1192   newivs_index = htab_create (10, clast_name_index_elt_info,
1193                               eq_clast_name_indexes, free);
1194
1195   new_scop_exit_edge = translate_clast (region, context_loop, pc.stmt,
1196                                         if_region->true_region->entry,
1197                                         rename_map, &newivs, newivs_index,
1198                                         bb_pbb_mapping);
1199   sese_reset_aux_in_loops (region);
1200   graphite_verify ();
1201   sese_adjust_liveout_phis (region, rename_map,
1202                             if_region->region->exit->src,
1203                             if_region->false_region->exit,
1204                             if_region->true_region->exit);
1205   recompute_all_dominators ();
1206   graphite_verify ();
1207
1208   htab_delete (rename_map);
1209   htab_delete (newivs_index);
1210   VEC_free (tree, heap, newivs);
1211   cloog_clast_free (pc.stmt);
1212   cloog_program_free (pc.prog);
1213   timevar_pop (TV_GRAPHITE_CODE_GEN);
1214
1215   return true;
1216 }
1217
1218 \f
1219
1220 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING.  */
1221
1222 static poly_bb_p
1223 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
1224 {
1225   bb_pbb_def tmp;
1226   PTR *slot;
1227
1228   tmp.bb = bb;
1229   slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
1230
1231   if (slot && *slot)
1232     return ((bb_pbb_def *) *slot)->pbb;
1233
1234   return NULL;
1235 }
1236
1237 /* Free loop->aux in newly created loops by translate_clast.  */
1238
1239 void
1240 free_aux_in_new_loops (void)
1241 {
1242   loop_p loop;
1243   loop_iterator li;
1244
1245   FOR_EACH_LOOP (li, loop, 0)
1246     {
1247       if (!loop->aux)
1248         continue;
1249       free(loop->aux);
1250       loop->aux = NULL;
1251     }
1252 }
1253
1254 /* Check data dependency in LOOP. BB_PBB_MAPPING is a basic_block and
1255    it's related poly_bb_p mapping.
1256 */
1257
1258 static bool
1259 dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping)
1260 {
1261   unsigned i,j;
1262   int level = 0;
1263   basic_block *bbs = get_loop_body_in_dom_order (loop);
1264
1265   level = *((int *)(loop->aux));
1266
1267   for (i = 0; i < loop->num_nodes; i++)
1268     {
1269       poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
1270
1271       if (pbb1 == NULL)
1272        continue;
1273
1274       for (j = 0; j < loop->num_nodes; j++)
1275        {
1276          poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
1277
1278          if (pbb2 == NULL)
1279            continue;
1280
1281          if (dependency_between_pbbs_p (pbb1, pbb2, level))
1282            {
1283              free (bbs);
1284              return true;
1285            }
1286        }
1287     }
1288
1289   free (bbs);
1290
1291   return false;
1292 }
1293
1294 /* Mark loop as parallel if data dependency does not exist.
1295    BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1296 */
1297
1298 void mark_loops_parallel (htab_t bb_pbb_mapping)
1299 {
1300   loop_p loop;
1301   loop_iterator li;
1302   int num_no_dependency = 0;
1303
1304   FOR_EACH_LOOP (li, loop, 0)
1305     {
1306       if (!loop->aux)
1307         continue;
1308
1309       if (!dependency_in_loop_p (loop, bb_pbb_mapping))
1310         {
1311           loop->can_be_parallel = true;
1312           num_no_dependency++;
1313         }
1314     }
1315
1316   if (dump_file && (dump_flags & TDF_DETAILS))
1317     {
1318       fprintf (dump_file, "\n%d loops carried no dependency.\n",
1319                num_no_dependency);
1320     }
1321 }
1322
1323 #endif