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