1/* Translation of CLAST (CLooG AST) to Gimple. 2 Copyright (C) 2009, 2010 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <sebastian.pop@amd.com>. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 3, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along 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/* This flag is set when an error occurred during the translation of 56 CLAST to Gimple. */ 57static bool gloog_error; 58 59/* Verifies properties that GRAPHITE should maintain during translation. */ 60 61static inline void 62graphite_verify (void) 63{ 64#ifdef ENABLE_CHECKING 65 verify_loop_structure (); 66 verify_dominators (CDI_DOMINATORS); 67 verify_dominators (CDI_POST_DOMINATORS); 68 verify_ssa (false); 69 verify_loop_closed_ssa (); 70#endif 71} 72 73/* Stores the INDEX in a vector for a given clast NAME. */ 74 75typedef struct clast_name_index { 76 int index; 77 const char *name; 78} *clast_name_index_p; 79 80/* Returns a pointer to a new element of type clast_name_index_p built 81 from NAME and INDEX. */ 82 83static inline clast_name_index_p 84new_clast_name_index (const char *name, int index) 85{ 86 clast_name_index_p res = XNEW (struct clast_name_index); 87 88 res->name = name; 89 res->index = index; 90 return res; 91} 92 93/* For a given clast NAME, returns -1 if it does not correspond to any 94 parameter, or otherwise, returns the index in the PARAMS or 95 SCATTERING_DIMENSIONS vector. */ 96 97static inline int 98clast_name_to_index (const char *name, htab_t index_table) 99{ 100 struct clast_name_index tmp; 101 PTR *slot; 102 103 tmp.name = name; 104 slot = htab_find_slot (index_table, &tmp, NO_INSERT); 105 106 if (slot && *slot) 107 return ((struct clast_name_index *) *slot)->index; 108 109 return -1; 110} 111 112/* Records in INDEX_TABLE the INDEX for NAME. */ 113 114static inline void 115save_clast_name_index (htab_t index_table, const char *name, int index) 116{ 117 struct clast_name_index tmp; 118 PTR *slot; 119 120 tmp.name = name; 121 slot = htab_find_slot (index_table, &tmp, INSERT); 122 123 if (slot) 124 { 125 if (*slot) 126 free (*slot); 127 128 *slot = new_clast_name_index (name, index); 129 } 130} 131 132/* Print to stderr the element ELT. */ 133 134static inline void 135debug_clast_name_index (clast_name_index_p elt) 136{ 137 fprintf (stderr, "(index = %d, name = %s)\n", elt->index, elt->name); 138} 139 140/* Helper function for debug_rename_map. */ 141 142static inline int 143debug_clast_name_indexes_1 (void **slot, void *s ATTRIBUTE_UNUSED) 144{ 145 struct clast_name_index *entry = (struct clast_name_index *) *slot; 146 debug_clast_name_index (entry); 147 return 1; 148} 149 150/* Print to stderr all the elements of MAP. */ 151 152void 153debug_clast_name_indexes (htab_t map) 154{ 155 htab_traverse (map, debug_clast_name_indexes_1, NULL); 156} 157 158/* Computes a hash function for database element ELT. */ 159 160static inline hashval_t 161clast_name_index_elt_info (const void *elt) 162{ 163 return htab_hash_pointer (((const struct clast_name_index *) elt)->name); 164} 165 166/* Compares database elements E1 and E2. */ 167 168static inline int 169eq_clast_name_indexes (const void *e1, const void *e2) 170{ 171 const struct clast_name_index *elt1 = (const struct clast_name_index *) e1; 172 const struct clast_name_index *elt2 = (const struct clast_name_index *) e2; 173 174 return (elt1->name == elt2->name); 175} 176 177 178/* For a given loop DEPTH in the loop nest of the original black box 179 PBB, return the old induction variable associated to that loop. */ 180 181static inline tree 182pbb_to_depth_to_oldiv (poly_bb_p pbb, int depth) 183{ 184 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); 185 sese region = SCOP_REGION (PBB_SCOP (pbb)); 186 loop_p loop = gbb_loop_at_index (gbb, region, depth); 187 188 return loop->single_iv; 189} 190 191/* For a given scattering dimension, return the new induction variable 192 associated to it. */ 193 194static inline tree 195newivs_to_depth_to_newiv (VEC (tree, heap) *newivs, int depth) 196{ 197 return VEC_index (tree, newivs, depth); 198} 199 200 201 202/* Returns the tree variable from the name NAME that was given in 203 Cloog representation. */ 204 205static tree 206clast_name_to_gcc (const char *name, sese region, VEC (tree, heap) *newivs, 207 htab_t newivs_index, htab_t params_index) 208{ 209 int index; 210 VEC (tree, heap) *params = SESE_PARAMS (region); 211 212 if (params && params_index) 213 { 214 index = clast_name_to_index (name, params_index); 215 216 if (index >= 0) 217 return VEC_index (tree, params, index); 218 } 219 220 gcc_assert (newivs && newivs_index); 221 index = clast_name_to_index (name, newivs_index); 222 gcc_assert (index >= 0); 223 224 return newivs_to_depth_to_newiv (newivs, index); 225} 226 227/* Returns the maximal precision type for expressions E1 and E2. */ 228 229static inline tree 230max_precision_type (tree e1, tree e2) 231{ 232 tree type1 = TREE_TYPE (e1); 233 tree type2 = TREE_TYPE (e2); 234 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2; 235} 236 237static tree 238clast_to_gcc_expression (tree, struct clast_expr *, sese, VEC (tree, heap) *, 239 htab_t, htab_t); 240 241/* Converts a Cloog reduction expression R with reduction operation OP 242 to a GCC expression tree of type TYPE. */ 243 244static tree 245clast_to_gcc_expression_red (tree type, enum tree_code op, 246 struct clast_reduction *r, 247 sese region, VEC (tree, heap) *newivs, 248 htab_t newivs_index, htab_t params_index) 249{ 250 int i; 251 tree res = clast_to_gcc_expression (type, r->elts[0], region, newivs, 252 newivs_index, params_index); 253 tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type; 254 255 for (i = 1; i < r->n; i++) 256 { 257 tree t = clast_to_gcc_expression (operand_type, r->elts[i], region, 258 newivs, newivs_index, params_index); 259 res = fold_build2 (op, type, res, t); 260 } 261 262 return res; 263} 264 265/* Converts a Cloog AST expression E back to a GCC expression tree of 266 type TYPE. */ 267 268static tree 269clast_to_gcc_expression (tree type, struct clast_expr *e, 270 sese region, VEC (tree, heap) *newivs, 271 htab_t newivs_index, htab_t params_index) 272{ 273 switch (e->type) 274 { 275 case expr_term: 276 { 277 struct clast_term *t = (struct clast_term *) e; 278 279 if (t->var) 280 { 281 if (value_one_p (t->val)) 282 { 283 tree name = clast_name_to_gcc (t->var, region, newivs, 284 newivs_index, params_index); 285 286 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type)) 287 name = fold_convert (sizetype, name); 288 289 name = fold_convert (type, name); 290 return name; 291 } 292 293 else if (value_mone_p (t->val)) 294 { 295 tree name = clast_name_to_gcc (t->var, region, newivs, 296 newivs_index, params_index); 297 298 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type)) 299 name = fold_convert (sizetype, name); 300 301 name = fold_convert (type, name); 302 303 return fold_build1 (NEGATE_EXPR, type, name); 304 } 305 else 306 { 307 tree name = clast_name_to_gcc (t->var, region, newivs, 308 newivs_index, params_index); 309 tree cst = gmp_cst_to_tree (type, t->val); 310 311 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type)) 312 name = fold_convert (sizetype, name); 313 314 name = fold_convert (type, name); 315 316 if (!POINTER_TYPE_P (type)) 317 return fold_build2 (MULT_EXPR, type, cst, name); 318 319 gloog_error = true; 320 return cst; 321 } 322 } 323 else 324 return gmp_cst_to_tree (type, t->val); 325 } 326 327 case expr_red: 328 { 329 struct clast_reduction *r = (struct clast_reduction *) e; 330 331 switch (r->type) 332 { 333 case clast_red_sum: 334 return clast_to_gcc_expression_red 335 (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR, 336 r, region, newivs, newivs_index, params_index); 337 338 case clast_red_min: 339 return clast_to_gcc_expression_red (type, MIN_EXPR, r, region, 340 newivs, newivs_index, 341 params_index); 342 343 case clast_red_max: 344 return clast_to_gcc_expression_red (type, MAX_EXPR, r, region, 345 newivs, newivs_index, 346 params_index); 347 348 default: 349 gcc_unreachable (); 350 } 351 break; 352 } 353 354 case expr_bin: 355 { 356 struct clast_binary *b = (struct clast_binary *) e; 357 struct clast_expr *lhs = (struct clast_expr *) b->LHS; 358 tree tl = clast_to_gcc_expression (type, lhs, region, newivs, 359 newivs_index, params_index); 360 tree tr = gmp_cst_to_tree (type, b->RHS); 361 362 switch (b->type) 363 { 364 case clast_bin_fdiv: 365 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr); 366 367 case clast_bin_cdiv: 368 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr); 369 370 case clast_bin_div: 371 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr); 372 373 case clast_bin_mod: 374 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr); 375 376 default: 377 gcc_unreachable (); 378 } 379 } 380 381 default: 382 gcc_unreachable (); 383 } 384 385 return NULL_TREE; 386} 387 388/* Returns the type for the expression E. */ 389 390static tree 391gcc_type_for_clast_expr (struct clast_expr *e, 392 sese region, VEC (tree, heap) *newivs, 393 htab_t newivs_index, htab_t params_index) 394{ 395 switch (e->type) 396 { 397 case expr_term: 398 { 399 struct clast_term *t = (struct clast_term *) e; 400 401 if (t->var) 402 return TREE_TYPE (clast_name_to_gcc (t->var, region, newivs, 403 newivs_index, params_index)); 404 else 405 return NULL_TREE; 406 } 407 408 case expr_red: 409 { 410 struct clast_reduction *r = (struct clast_reduction *) e; 411 412 if (r->n == 1) 413 return gcc_type_for_clast_expr (r->elts[0], region, newivs, 414 newivs_index, params_index); 415 else 416 { 417 int i; 418 for (i = 0; i < r->n; i++) 419 { 420 tree type = gcc_type_for_clast_expr (r->elts[i], region, 421 newivs, newivs_index, 422 params_index); 423 if (type) 424 return type; 425 } 426 return NULL_TREE; 427 } 428 } 429 430 case expr_bin: 431 { 432 struct clast_binary *b = (struct clast_binary *) e; 433 struct clast_expr *lhs = (struct clast_expr *) b->LHS; 434 return gcc_type_for_clast_expr (lhs, region, newivs, 435 newivs_index, params_index); 436 } 437 438 default: 439 gcc_unreachable (); 440 } 441 442 return NULL_TREE; 443} 444 445/* Returns the type for the equation CLEQ. */ 446 447static tree 448gcc_type_for_clast_eq (struct clast_equation *cleq, 449 sese region, VEC (tree, heap) *newivs, 450 htab_t newivs_index, htab_t params_index) 451{ 452 tree type = gcc_type_for_clast_expr (cleq->LHS, region, newivs, 453 newivs_index, params_index); 454 if (type) 455 return type; 456 457 return gcc_type_for_clast_expr (cleq->RHS, region, newivs, newivs_index, 458 params_index); 459} 460 461/* Translates a clast equation CLEQ to a tree. */ 462 463static tree 464graphite_translate_clast_equation (sese region, 465 struct clast_equation *cleq, 466 VEC (tree, heap) *newivs, 467 htab_t newivs_index, htab_t params_index) 468{ 469 enum tree_code comp; 470 tree type = gcc_type_for_clast_eq (cleq, region, newivs, newivs_index, 471 params_index); 472 tree lhs = clast_to_gcc_expression (type, cleq->LHS, region, newivs, 473 newivs_index, params_index); 474 tree rhs = clast_to_gcc_expression (type, cleq->RHS, region, newivs, 475 newivs_index, params_index); 476 477 if (cleq->sign == 0) 478 comp = EQ_EXPR; 479 480 else if (cleq->sign > 0) 481 comp = GE_EXPR; 482 483 else 484 comp = LE_EXPR; 485 486 return fold_build2 (comp, boolean_type_node, lhs, rhs); 487} 488 489/* Creates the test for the condition in STMT. */ 490 491static tree 492graphite_create_guard_cond_expr (sese region, struct clast_guard *stmt, 493 VEC (tree, heap) *newivs, 494 htab_t newivs_index, htab_t params_index) 495{ 496 tree cond = NULL; 497 int i; 498 499 for (i = 0; i < stmt->n; i++) 500 { 501 tree eq = graphite_translate_clast_equation (region, &stmt->eq[i], 502 newivs, newivs_index, 503 params_index); 504 505 if (cond) 506 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq); 507 else 508 cond = eq; 509 } 510 511 return cond; 512} 513 514/* Creates a new if region corresponding to Cloog's guard. */ 515 516static edge 517graphite_create_new_guard (sese region, edge entry_edge, 518 struct clast_guard *stmt, 519 VEC (tree, heap) *newivs, 520 htab_t newivs_index, htab_t params_index) 521{ 522 tree cond_expr = graphite_create_guard_cond_expr (region, stmt, newivs, 523 newivs_index, params_index); 524 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); 525 return exit_edge; 526} 527 528/* Walks a CLAST and returns the first statement in the body of a 529 loop. */ 530 531static struct clast_user_stmt * 532clast_get_body_of_loop (struct clast_stmt *stmt) 533{ 534 if (!stmt 535 || CLAST_STMT_IS_A (stmt, stmt_user)) 536 return (struct clast_user_stmt *) stmt; 537 538 if (CLAST_STMT_IS_A (stmt, stmt_for)) 539 return clast_get_body_of_loop (((struct clast_for *) stmt)->body); 540 541 if (CLAST_STMT_IS_A (stmt, stmt_guard)) 542 return clast_get_body_of_loop (((struct clast_guard *) stmt)->then); 543 544 if (CLAST_STMT_IS_A (stmt, stmt_block)) 545 return clast_get_body_of_loop (((struct clast_block *) stmt)->body); 546 547 gcc_unreachable (); 548} 549 550/* Java does not initialize long_long_integer_type_node. */ 551#define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype) 552 553/* Given a CLOOG_IV, return the type that CLOOG_IV should have in GCC 554 land. The selected type is big enough to include the original loop 555 iteration variable, but signed to work with the subtractions CLooG 556 may have introduced. If such a type is not available, we fail. 557 558 TODO: Do not always return long_long, but the smallest possible 559 type, that still holds the original type. 560 561 TODO: Get the types using CLooG instead. This enables further 562 optimizations, but needs CLooG support. */ 563 564static tree 565gcc_type_for_cloog_iv (const char *cloog_iv, gimple_bb_p gbb) 566{ 567 struct ivtype_map_elt_s tmp; 568 PTR *slot; 569 570 tmp.cloog_iv = cloog_iv; 571 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT); 572 573 if (slot && *slot) 574 { 575 tree type = ((ivtype_map_elt) *slot)->type; 576 int type_precision = TYPE_PRECISION (type); 577 578 /* Find the smallest signed type possible. */ 579 if (!TYPE_UNSIGNED (type)) 580 { 581 if (type_precision <= TYPE_PRECISION (integer_type_node)) 582 return integer_type_node; 583 584 if (type_precision <= TYPE_PRECISION (long_integer_type_node)) 585 return long_integer_type_node; 586 587 if (type_precision <= TYPE_PRECISION (my_long_long)) 588 return my_long_long; 589 590 gcc_unreachable (); 591 } 592 593 if (type_precision < TYPE_PRECISION (integer_type_node)) 594 return integer_type_node; 595 596 if (type_precision < TYPE_PRECISION (long_integer_type_node)) 597 return long_integer_type_node; 598 599 if (type_precision < TYPE_PRECISION (my_long_long)) 600 return my_long_long; 601 602 /* There is no signed type available, that is large enough to hold the 603 original value. */ 604 gcc_unreachable (); 605 } 606 607 return my_long_long; 608} 609 610#undef my_long_long 611 612/* Returns the induction variable for the loop that gets translated to 613 STMT. */ 614 615static tree 616gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for) 617{ 618 struct clast_stmt *stmt = (struct clast_stmt *) stmt_for; 619 struct clast_user_stmt *body = clast_get_body_of_loop (stmt); 620 const char *cloog_iv = stmt_for->iterator; 621 CloogStatement *cs = body->statement; 622 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs); 623 624 return gcc_type_for_cloog_iv (cloog_iv, PBB_BLACK_BOX (pbb)); 625} 626 627/* Creates a new LOOP corresponding to Cloog's STMT. Inserts an 628 induction variable for the new LOOP. New LOOP is attached to CFG 629 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and 630 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds 631 CLooG's scattering name to the induction variable created for the 632 loop of STMT. The new induction variable is inserted in the NEWIVS 633 vector. */ 634 635static struct loop * 636graphite_create_new_loop (sese region, edge entry_edge, 637 struct clast_for *stmt, 638 loop_p outer, VEC (tree, heap) **newivs, 639 htab_t newivs_index, htab_t params_index) 640{ 641 tree type = gcc_type_for_iv_of_clast_loop (stmt); 642 tree lb = clast_to_gcc_expression (type, stmt->LB, region, *newivs, 643 newivs_index, params_index); 644 tree ub = clast_to_gcc_expression (type, stmt->UB, region, *newivs, 645 newivs_index, params_index); 646 tree stride = gmp_cst_to_tree (type, stmt->stride); 647 tree ivvar = create_tmp_var (type, "graphite_IV"); 648 tree iv, iv_after_increment; 649 loop_p loop = create_empty_loop_on_edge 650 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment, 651 outer ? outer : entry_edge->src->loop_father); 652 653 add_referenced_var (ivvar); 654 655 save_clast_name_index (newivs_index, stmt->iterator, 656 VEC_length (tree, *newivs)); 657 VEC_safe_push (tree, heap, *newivs, iv); 658 return loop; 659} 660 661/* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction 662 variables of the loops around GBB in SESE. */ 663 664static void 665build_iv_mapping (htab_t map, sese region, 666 VEC (tree, heap) *newivs, htab_t newivs_index, 667 struct clast_user_stmt *user_stmt, 668 htab_t params_index) 669{ 670 struct clast_stmt *t; 671 int index = 0; 672 CloogStatement *cs = user_stmt->statement; 673 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs); 674 675 for (t = user_stmt->substitutions; t; t = t->next, index++) 676 { 677 struct clast_expr *expr = (struct clast_expr *) 678 ((struct clast_assignment *)t)->RHS; 679 tree type = gcc_type_for_clast_expr (expr, region, newivs, 680 newivs_index, params_index); 681 tree old_name = pbb_to_depth_to_oldiv (pbb, index); 682 tree e = clast_to_gcc_expression (type, expr, region, newivs, 683 newivs_index, params_index); 684 set_rename (map, old_name, e); 685 } 686} 687 688/* Helper function for htab_traverse. */ 689 690static int 691copy_renames (void **slot, void *s) 692{ 693 struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot; 694 htab_t res = (htab_t) s; 695 tree old_name = entry->old_name; 696 tree expr = entry->expr; 697 struct rename_map_elt_s tmp; 698 PTR *x; 699 700 tmp.old_name = old_name; 701 x = htab_find_slot (res, &tmp, INSERT); 702 703 if (x && !*x) 704 *x = new_rename_map_elt (old_name, expr); 705 706 return 1; 707} 708 709/* Construct bb_pbb_def with BB and PBB. */ 710 711static bb_pbb_def * 712new_bb_pbb_def (basic_block bb, poly_bb_p pbb) 713{ 714 bb_pbb_def *bb_pbb_p; 715 716 bb_pbb_p = XNEW (bb_pbb_def); 717 bb_pbb_p->bb = bb; 718 bb_pbb_p->pbb = pbb; 719 720 return bb_pbb_p; 721} 722 723/* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */ 724 725static void 726mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping) 727{ 728 bb_pbb_def tmp; 729 PTR *x; 730 731 tmp.bb = bb; 732 x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT); 733 734 if (x && !*x) 735 *x = new_bb_pbb_def (bb, pbb); 736} 737 738/* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */ 739 740static poly_bb_p 741find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb) 742{ 743 bb_pbb_def tmp; 744 PTR *slot; 745 746 tmp.bb = bb; 747 slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT); 748 749 if (slot && *slot) 750 return ((bb_pbb_def *) *slot)->pbb; 751 752 return NULL; 753} 754 755/* Check data dependency in LOOP at scattering level LEVEL. 756 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p 757 mapping. */ 758 759static bool 760dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level) 761{ 762 unsigned i,j; 763 basic_block *bbs = get_loop_body_in_dom_order (loop); 764 765 for (i = 0; i < loop->num_nodes; i++) 766 { 767 poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]); 768 769 if (pbb1 == NULL) 770 continue; 771 772 for (j = 0; j < loop->num_nodes; j++) 773 { 774 poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]); 775 776 if (pbb2 == NULL) 777 continue; 778 779 if (dependency_between_pbbs_p (pbb1, pbb2, level)) 780 { 781 free (bbs); 782 return true; 783 } 784 } 785 } 786 787 free (bbs); 788 789 return false; 790} 791 792static edge 793translate_clast (sese, loop_p, struct clast_stmt *, edge, htab_t, 794 VEC (tree, heap) **, htab_t, htab_t, int, htab_t); 795 796/* Translates a clast user statement STMT to gimple. 797 798 - REGION is the sese region we used to generate the scop. 799 - NEXT_E is the edge where new generated code should be attached. 800 - CONTEXT_LOOP is the loop in which the generated code will be placed 801 - RENAME_MAP contains a set of tuples of new names associated to 802 the original variables names. 803 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. 804 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in 805 the sese region. */ 806static edge 807translate_clast_user (sese region, struct clast_user_stmt *stmt, edge next_e, 808 htab_t rename_map, VEC (tree, heap) **newivs, 809 htab_t newivs_index, htab_t bb_pbb_mapping, 810 htab_t params_index) 811{ 812 gimple_bb_p gbb; 813 basic_block new_bb; 814 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement); 815 gbb = PBB_BLACK_BOX (pbb); 816 817 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR) 818 return next_e; 819 820 build_iv_mapping (rename_map, region, *newivs, newivs_index, stmt, 821 params_index); 822 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region, 823 next_e, rename_map); 824 new_bb = next_e->src; 825 mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping); 826 update_ssa (TODO_update_ssa); 827 828 return next_e; 829} 830 831/* Creates a new if region protecting the loop to be executed, if the execution 832 count is zero (lb > ub). */ 833static edge 834graphite_create_new_loop_guard (sese region, edge entry_edge, 835 struct clast_for *stmt, 836 VEC (tree, heap) *newivs, 837 htab_t newivs_index, htab_t params_index) 838{ 839 tree cond_expr; 840 edge exit_edge; 841 tree type = gcc_type_for_iv_of_clast_loop (stmt); 842 tree lb = clast_to_gcc_expression (type, stmt->LB, region, newivs, 843 newivs_index, params_index); 844 tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs, 845 newivs_index, params_index); 846 847 /* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a 848 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes 849 2^{32|64}, and the condition lb <= ub is true, even if we do not want this. 850 However lb < ub + 1 is false, as expected. 851 There might be a problem with cases where ub is 2^32. */ 852 tree one; 853 Value gmp_one; 854 value_init (gmp_one); 855 value_set_si (gmp_one, 1); 856 one = gmp_cst_to_tree (type, gmp_one); 857 value_clear (gmp_one); 858 859 ub = fold_build2 (PLUS_EXPR, type, ub, one); 860 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub); 861 862 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); 863 864 return exit_edge; 865} 866 867 868/* Create the loop for a clast for statement. 869 870 - REGION is the sese region we used to generate the scop. 871 - NEXT_E is the edge where new generated code should be attached. 872 - RENAME_MAP contains a set of tuples of new names associated to 873 the original variables names. 874 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. 875 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in 876 the sese region. */ 877static edge 878translate_clast_for_loop (sese region, loop_p context_loop, 879 struct clast_for *stmt, edge next_e, 880 htab_t rename_map, VEC (tree, heap) **newivs, 881 htab_t newivs_index, htab_t bb_pbb_mapping, 882 int level, htab_t params_index) 883{ 884 struct loop *loop = graphite_create_new_loop (region, next_e, stmt, 885 context_loop, newivs, 886 newivs_index, params_index); 887 edge last_e = single_exit (loop); 888 edge to_body = single_succ_edge (loop->header); 889 basic_block after = to_body->dest; 890 891 /* Create a basic block for loop close phi nodes. */ 892 last_e = single_succ_edge (split_edge (last_e)); 893 894 /* Translate the body of the loop. */ 895 next_e = translate_clast (region, loop, stmt->body, to_body, rename_map, 896 newivs, newivs_index, bb_pbb_mapping, level + 1, 897 params_index); 898 redirect_edge_succ_nodup (next_e, after); 899 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src); 900 901 /* Remove from rename_map all the tuples containing variables 902 defined in loop's body. */ 903 insert_loop_close_phis (rename_map, loop); 904 905 if (flag_loop_parallelize_all 906 && !dependency_in_loop_p (loop, bb_pbb_mapping, 907 get_scattering_level (level))) 908 loop->can_be_parallel = true; 909 910 return last_e; 911} 912 913/* Translates a clast for statement STMT to gimple. First a guard is created 914 protecting the loop, if it is executed zero times. In this guard we create 915 the real loop structure. 916 917 - REGION is the sese region we used to generate the scop. 918 - NEXT_E is the edge where new generated code should be attached. 919 - RENAME_MAP contains a set of tuples of new names associated to 920 the original variables names. 921 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. 922 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in 923 the sese region. */ 924static edge 925translate_clast_for (sese region, loop_p context_loop, struct clast_for *stmt, 926 edge next_e, htab_t rename_map, VEC (tree, heap) **newivs, 927 htab_t newivs_index, htab_t bb_pbb_mapping, int level, 928 htab_t params_index) 929{ 930 edge last_e = graphite_create_new_loop_guard (region, next_e, stmt, *newivs, 931 newivs_index, params_index); 932 933 edge true_e = get_true_edge_from_guard_bb (next_e->dest); 934 edge false_e = get_false_edge_from_guard_bb (next_e->dest); 935 edge exit_true_e = single_succ_edge (true_e->dest); 936 edge exit_false_e = single_succ_edge (false_e->dest); 937 938 htab_t before_guard = htab_create (10, rename_map_elt_info, 939 eq_rename_map_elts, free); 940 htab_traverse (rename_map, copy_renames, before_guard); 941 942 next_e = translate_clast_for_loop (region, context_loop, stmt, true_e, 943 rename_map, newivs, 944 newivs_index, bb_pbb_mapping, level, 945 params_index); 946 947 insert_guard_phis (last_e->src, exit_true_e, exit_false_e, 948 before_guard, rename_map); 949 950 htab_delete (before_guard); 951 952 return last_e; 953} 954 955/* Translates a clast guard statement STMT to gimple. 956 957 - REGION is the sese region we used to generate the scop. 958 - NEXT_E is the edge where new generated code should be attached. 959 - CONTEXT_LOOP is the loop in which the generated code will be placed 960 - RENAME_MAP contains a set of tuples of new names associated to 961 the original variables names. 962 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. 963 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in 964 the sese region. */ 965static edge 966translate_clast_guard (sese region, loop_p context_loop, 967 struct clast_guard *stmt, edge next_e, 968 htab_t rename_map, VEC (tree, heap) **newivs, 969 htab_t newivs_index, htab_t bb_pbb_mapping, int level, 970 htab_t params_index) 971{ 972 edge last_e = graphite_create_new_guard (region, next_e, stmt, *newivs, 973 newivs_index, params_index); 974 975 edge true_e = get_true_edge_from_guard_bb (next_e->dest); 976 edge false_e = get_false_edge_from_guard_bb (next_e->dest); 977 edge exit_true_e = single_succ_edge (true_e->dest); 978 edge exit_false_e = single_succ_edge (false_e->dest); 979 980 htab_t before_guard = htab_create (10, rename_map_elt_info, 981 eq_rename_map_elts, free); 982 htab_traverse (rename_map, copy_renames, before_guard); 983 984 next_e = translate_clast (region, context_loop, stmt->then, true_e, 985 rename_map, newivs, newivs_index, bb_pbb_mapping, 986 level, params_index); 987 988 insert_guard_phis (last_e->src, exit_true_e, exit_false_e, 989 before_guard, rename_map); 990 991 htab_delete (before_guard); 992 993 return last_e; 994} 995 996/* Translates a CLAST statement STMT to GCC representation in the 997 context of a SESE. 998 999 - NEXT_E is the edge where new generated code should be attached. 1000 - CONTEXT_LOOP is the loop in which the generated code will be placed 1001 - RENAME_MAP contains a set of tuples of new names associated to 1002 the original variables names. 1003 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */ 1004static edge 1005translate_clast (sese region, loop_p context_loop, struct clast_stmt *stmt, 1006 edge next_e, htab_t rename_map, VEC (tree, heap) **newivs, 1007 htab_t newivs_index, htab_t bb_pbb_mapping, int level, 1008 htab_t params_index) 1009{ 1010 if (!stmt) 1011 return next_e; 1012 1013 if (CLAST_STMT_IS_A (stmt, stmt_root)) 1014 ; /* Do nothing. */ 1015 1016 else if (CLAST_STMT_IS_A (stmt, stmt_user)) 1017 next_e = translate_clast_user (region, (struct clast_user_stmt *) stmt, 1018 next_e, rename_map, newivs, newivs_index, 1019 bb_pbb_mapping, params_index); 1020 1021 else if (CLAST_STMT_IS_A (stmt, stmt_for)) 1022 next_e = translate_clast_for (region, context_loop, 1023 (struct clast_for *) stmt, next_e, 1024 rename_map, newivs, newivs_index, 1025 bb_pbb_mapping, level, params_index); 1026 1027 else if (CLAST_STMT_IS_A (stmt, stmt_guard)) 1028 next_e = translate_clast_guard (region, context_loop, 1029 (struct clast_guard *) stmt, next_e, 1030 rename_map, newivs, newivs_index, 1031 bb_pbb_mapping, level, params_index); 1032 1033 else if (CLAST_STMT_IS_A (stmt, stmt_block)) 1034 next_e = translate_clast (region, context_loop, 1035 ((struct clast_block *) stmt)->body, 1036 next_e, rename_map, newivs, newivs_index, 1037 bb_pbb_mapping, level, params_index); 1038 else 1039 gcc_unreachable(); 1040 1041 recompute_all_dominators (); 1042 graphite_verify (); 1043 1044 return translate_clast (region, context_loop, stmt->next, next_e, 1045 rename_map, newivs, newivs_index, 1046 bb_pbb_mapping, level, params_index); 1047} 1048 1049/* Returns the first cloog name used in EXPR. */ 1050 1051static const char * 1052find_cloog_iv_in_expr (struct clast_expr *expr) 1053{ 1054 struct clast_term *term = (struct clast_term *) expr; 1055 struct clast_reduction *red; 1056 int i; 1057 1058 if (expr->type == expr_term) 1059 return term->var; 1060 1061 if (expr->type != expr_red) 1062 return NULL; 1063 1064 red = (struct clast_reduction *) expr; 1065 for (i = 0; i < red->n; i++) 1066 { 1067 const char *res = find_cloog_iv_in_expr (red->elts[i]); 1068 1069 if (res) 1070 return res; 1071 } 1072 1073 return NULL; 1074} 1075 1076/* Build for USER_STMT a map between the CLAST induction variables and 1077 the corresponding GCC old induction variables. This information is 1078 stored on each GRAPHITE_BB. */ 1079 1080static void 1081compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt) 1082{ 1083 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); 1084 struct clast_stmt *t; 1085 int index = 0; 1086 1087 for (t = user_stmt->substitutions; t; t = t->next, index++) 1088 { 1089 PTR *slot; 1090 struct ivtype_map_elt_s tmp; 1091 struct clast_expr *expr = (struct clast_expr *) 1092 ((struct clast_assignment *)t)->RHS; 1093 1094 /* Create an entry (clast_var, type). */ 1095 tmp.cloog_iv = find_cloog_iv_in_expr (expr); 1096 if (!tmp.cloog_iv) 1097 continue; 1098 1099 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT); 1100 1101 if (slot && !*slot) 1102 { 1103 tree oldiv = pbb_to_depth_to_oldiv (pbb, index); 1104 tree type = TREE_TYPE (oldiv); 1105 *slot = new_ivtype_map_elt (tmp.cloog_iv, type); 1106 } 1107 } 1108} 1109 1110/* Walk the CLAST tree starting from STMT and build for each 1111 clast_user_stmt a map between the CLAST induction variables and the 1112 corresponding GCC old induction variables. This information is 1113 stored on each GRAPHITE_BB. */ 1114 1115static void 1116compute_cloog_iv_types (struct clast_stmt *stmt) 1117{ 1118 if (!stmt) 1119 return; 1120 1121 if (CLAST_STMT_IS_A (stmt, stmt_root)) 1122 goto next; 1123 1124 if (CLAST_STMT_IS_A (stmt, stmt_user)) 1125 { 1126 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement; 1127 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs); 1128 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); 1129 1130 if (!GBB_CLOOG_IV_TYPES (gbb)) 1131 GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info, 1132 eq_ivtype_map_elts, free); 1133 1134 compute_cloog_iv_types_1 (pbb, (struct clast_user_stmt *) stmt); 1135 goto next; 1136 } 1137 1138 if (CLAST_STMT_IS_A (stmt, stmt_for)) 1139 { 1140 struct clast_stmt *s = ((struct clast_for *) stmt)->body; 1141 compute_cloog_iv_types (s); 1142 goto next; 1143 } 1144 1145 if (CLAST_STMT_IS_A (stmt, stmt_guard)) 1146 { 1147 struct clast_stmt *s = ((struct clast_guard *) stmt)->then; 1148 compute_cloog_iv_types (s); 1149 goto next; 1150 } 1151 1152 if (CLAST_STMT_IS_A (stmt, stmt_block)) 1153 { 1154 struct clast_stmt *s = ((struct clast_block *) stmt)->body; 1155 compute_cloog_iv_types (s); 1156 goto next; 1157 } 1158 1159 gcc_unreachable (); 1160 1161 next: 1162 compute_cloog_iv_types (stmt->next); 1163} 1164 1165/* Free the SCATTERING domain list. */ 1166 1167static void 1168free_scattering (CloogDomainList *scattering) 1169{ 1170 while (scattering) 1171 { 1172 CloogDomain *dom = cloog_domain (scattering); 1173 CloogDomainList *next = cloog_next_domain (scattering); 1174 1175 cloog_domain_free (dom); 1176 free (scattering); 1177 scattering = next; 1178 } 1179} 1180 1181/* Initialize Cloog's parameter names from the names used in GIMPLE. 1182 Initialize Cloog's iterator names, using 'graphite_iterator_%d' 1183 from 0 to scop_nb_loops (scop). */ 1184 1185static void 1186initialize_cloog_names (scop_p scop, CloogProgram *prog) 1187{ 1188 sese region = SCOP_REGION (scop); 1189 int i; 1190 int nb_iterators = scop_max_loop_depth (scop); 1191 int nb_scattering = cloog_program_nb_scattdims (prog); 1192 int nb_parameters = VEC_length (tree, SESE_PARAMS (region)); 1193 char **iterators = XNEWVEC (char *, nb_iterators * 2); 1194 char **scattering = XNEWVEC (char *, nb_scattering); 1195 char **parameters= XNEWVEC (char *, nb_parameters); 1196 1197 cloog_program_set_names (prog, cloog_names_malloc ()); 1198 1199 for (i = 0; i < nb_parameters; i++) 1200 { 1201 tree param = VEC_index (tree, SESE_PARAMS(region), i); 1202 const char *name = get_name (param); 1203 int len; 1204 1205 if (!name) 1206 name = "T"; 1207 1208 len = strlen (name); 1209 len += 17; 1210 parameters[i] = XNEWVEC (char, len + 1); 1211 snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param)); 1212 } 1213 1214 cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters); 1215 cloog_names_set_parameters (cloog_program_names (prog), parameters); 1216 1217 for (i = 0; i < nb_iterators; i++) 1218 { 1219 int len = 4 + 16; 1220 iterators[i] = XNEWVEC (char, len); 1221 snprintf (iterators[i], len, "git_%d", i); 1222 } 1223 1224 cloog_names_set_nb_iterators (cloog_program_names (prog), 1225 nb_iterators); 1226 cloog_names_set_iterators (cloog_program_names (prog), 1227 iterators); 1228 1229 for (i = 0; i < nb_scattering; i++) 1230 { 1231 int len = 5 + 16; 1232 scattering[i] = XNEWVEC (char, len); 1233 snprintf (scattering[i], len, "scat_%d", i); 1234 } 1235 1236 cloog_names_set_nb_scattering (cloog_program_names (prog), 1237 nb_scattering); 1238 cloog_names_set_scattering (cloog_program_names (prog), 1239 scattering); 1240} 1241 1242/* Build cloog program for SCoP. */ 1243 1244static void 1245build_cloog_prog (scop_p scop, CloogProgram *prog) 1246{ 1247 int i; 1248 int max_nb_loops = scop_max_loop_depth (scop); 1249 poly_bb_p pbb; 1250 CloogLoop *loop_list = NULL; 1251 CloogBlockList *block_list = NULL; 1252 CloogDomainList *scattering = NULL; 1253 int nbs = 2 * max_nb_loops + 1; 1254 int *scaldims; 1255 1256 cloog_program_set_context 1257 (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop))); 1258 nbs = unify_scattering_dimensions (scop); 1259 scaldims = (int *) xmalloc (nbs * (sizeof (int))); 1260 cloog_program_set_nb_scattdims (prog, nbs); 1261 initialize_cloog_names (scop, prog); 1262 1263 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) 1264 { 1265 CloogStatement *stmt; 1266 CloogBlock *block; 1267 1268 /* Dead code elimination: when the domain of a PBB is empty, 1269 don't generate code for the PBB. */ 1270 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb))) 1271 continue; 1272 1273 /* Build the new statement and its block. */ 1274 stmt = cloog_statement_alloc (pbb_index (pbb)); 1275 block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb)); 1276 cloog_statement_set_usr (stmt, pbb); 1277 1278 /* Build loop list. */ 1279 { 1280 CloogLoop *new_loop_list = cloog_loop_malloc (); 1281 cloog_loop_set_next (new_loop_list, loop_list); 1282 cloog_loop_set_domain 1283 (new_loop_list, 1284 new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb))); 1285 cloog_loop_set_block (new_loop_list, block); 1286 loop_list = new_loop_list; 1287 } 1288 1289 /* Build block list. */ 1290 { 1291 CloogBlockList *new_block_list = cloog_block_list_malloc (); 1292 1293 cloog_block_list_set_next (new_block_list, block_list); 1294 cloog_block_list_set_block (new_block_list, block); 1295 block_list = new_block_list; 1296 } 1297 1298 /* Build scattering list. */ 1299 { 1300 /* XXX: Replace with cloog_domain_list_alloc(), when available. */ 1301 CloogDomainList *new_scattering 1302 = (CloogDomainList *) xmalloc (sizeof (CloogDomainList)); 1303 ppl_Polyhedron_t scat; 1304 CloogDomain *dom; 1305 1306 scat = PBB_TRANSFORMED_SCATTERING (pbb); 1307 dom = new_Cloog_Domain_from_ppl_Polyhedron (scat); 1308 1309 cloog_set_next_domain (new_scattering, scattering); 1310 cloog_set_domain (new_scattering, dom); 1311 scattering = new_scattering; 1312 } 1313 } 1314 1315 cloog_program_set_loop (prog, loop_list); 1316 cloog_program_set_blocklist (prog, block_list); 1317 1318 for (i = 0; i < nbs; i++) 1319 scaldims[i] = 0 ; 1320 1321 cloog_program_set_scaldims (prog, scaldims); 1322 1323 /* Extract scalar dimensions to simplify the code generation problem. */ 1324 cloog_program_extract_scalars (prog, scattering); 1325 1326 /* Apply scattering. */ 1327 cloog_program_scatter (prog, scattering); 1328 free_scattering (scattering); 1329 1330 /* Iterators corresponding to scalar dimensions have to be extracted. */ 1331 cloog_names_scalarize (cloog_program_names (prog), nbs, 1332 cloog_program_scaldims (prog)); 1333 1334 /* Free blocklist. */ 1335 { 1336 CloogBlockList *next = cloog_program_blocklist (prog); 1337 1338 while (next) 1339 { 1340 CloogBlockList *toDelete = next; 1341 next = cloog_block_list_next (next); 1342 cloog_block_list_set_next (toDelete, NULL); 1343 cloog_block_list_set_block (toDelete, NULL); 1344 cloog_block_list_free (toDelete); 1345 } 1346 cloog_program_set_blocklist (prog, NULL); 1347 } 1348} 1349 1350/* Return the options that will be used in GLOOG. */ 1351 1352static CloogOptions * 1353set_cloog_options (void) 1354{ 1355 CloogOptions *options = cloog_options_malloc (); 1356 1357 /* Change cloog output language to C. If we do use FORTRAN instead, cloog 1358 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if 1359 we pass an incomplete program to cloog. */ 1360 options->language = LANGUAGE_C; 1361 1362 /* Enable complex equality spreading: removes dummy statements 1363 (assignments) in the generated code which repeats the 1364 substitution equations for statements. This is useless for 1365 GLooG. */ 1366 options->esp = 1; 1367 1368 /* Enable C pretty-printing mode: normalizes the substitution 1369 equations for statements. */ 1370 options->cpp = 1; 1371 1372 /* Allow cloog to build strides with a stride width different to one. 1373 This example has stride = 4: 1374 1375 for (i = 0; i < 20; i += 4) 1376 A */ 1377 options->strides = 1; 1378 1379 /* Disable optimizations and make cloog generate source code closer to the 1380 input. This is useful for debugging, but later we want the optimized 1381 code. 1382 1383 XXX: We can not disable optimizations, as loop blocking is not working 1384 without them. */ 1385 if (0) 1386 { 1387 options->f = -1; 1388 options->l = INT_MAX; 1389 } 1390 1391 return options; 1392} 1393 1394/* Prints STMT to STDERR. */ 1395 1396void 1397print_clast_stmt (FILE *file, struct clast_stmt *stmt) 1398{ 1399 CloogOptions *options = set_cloog_options (); 1400 1401 pprint (file, stmt, 0, options); 1402 cloog_options_free (options); 1403} 1404 1405/* Prints STMT to STDERR. */ 1406 1407void 1408debug_clast_stmt (struct clast_stmt *stmt) 1409{ 1410 print_clast_stmt (stderr, stmt); 1411} 1412 1413/* Translate SCOP to a CLooG program and clast. These two 1414 representations should be freed together: a clast cannot be used 1415 without a program. */ 1416 1417cloog_prog_clast 1418scop_to_clast (scop_p scop) 1419{ 1420 CloogOptions *options = set_cloog_options (); 1421 cloog_prog_clast pc; 1422 1423 /* Connect new cloog prog generation to graphite. */ 1424 pc.prog = cloog_program_malloc (); 1425 build_cloog_prog (scop, pc.prog); 1426 pc.prog = cloog_program_generate (pc.prog, options); 1427 pc.stmt = cloog_clast_create (pc.prog, options); 1428 1429 cloog_options_free (options); 1430 return pc; 1431} 1432 1433/* Prints to FILE the code generated by CLooG for SCOP. */ 1434 1435void 1436print_generated_program (FILE *file, scop_p scop) 1437{ 1438 CloogOptions *options = set_cloog_options (); 1439 cloog_prog_clast pc = scop_to_clast (scop); 1440 1441 fprintf (file, " (prog: \n"); 1442 cloog_program_print (file, pc.prog); 1443 fprintf (file, " )\n"); 1444 1445 fprintf (file, " (clast: \n"); 1446 pprint (file, pc.stmt, 0, options); 1447 fprintf (file, " )\n"); 1448 1449 cloog_options_free (options); 1450 cloog_clast_free (pc.stmt); 1451 cloog_program_free (pc.prog); 1452} 1453 1454/* Prints to STDERR the code generated by CLooG for SCOP. */ 1455 1456void 1457debug_generated_program (scop_p scop) 1458{ 1459 print_generated_program (stderr, scop); 1460} 1461 1462/* Add CLooG names to parameter index. The index is used to translate 1463 back from CLooG names to GCC trees. */ 1464 1465static void 1466create_params_index (htab_t index_table, CloogProgram *prog) { 1467 CloogNames* names = cloog_program_names (prog); 1468 int nb_parameters = cloog_names_nb_parameters (names); 1469 char **parameters = cloog_names_parameters (names); 1470 int i; 1471 1472 for (i = 0; i < nb_parameters; i++) 1473 save_clast_name_index (index_table, parameters[i], i); 1474} 1475 1476/* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for 1477 the given SCOP. Return true if code generation succeeded. 1478 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping. 1479*/ 1480 1481bool 1482gloog (scop_p scop, VEC (scop_p, heap) *scops, htab_t bb_pbb_mapping) 1483{ 1484 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10); 1485 loop_p context_loop; 1486 sese region = SCOP_REGION (scop); 1487 ifsese if_region = NULL; 1488 htab_t rename_map, newivs_index, params_index; 1489 cloog_prog_clast pc; 1490 int i; 1491 1492 timevar_push (TV_GRAPHITE_CODE_GEN); 1493 gloog_error = false; 1494 1495 pc = scop_to_clast (scop); 1496 1497 if (dump_file && (dump_flags & TDF_DETAILS)) 1498 { 1499 fprintf (dump_file, "\nCLAST generated by CLooG: \n"); 1500 print_clast_stmt (dump_file, pc.stmt); 1501 fprintf (dump_file, "\n"); 1502 } 1503 1504 recompute_all_dominators (); 1505 graphite_verify (); 1506 1507 if_region = move_sese_in_condition (region); 1508 sese_insert_phis_for_liveouts (region, 1509 if_region->region->exit->src, 1510 if_region->false_region->exit, 1511 if_region->true_region->exit); 1512 recompute_all_dominators (); 1513 graphite_verify (); 1514 1515 context_loop = SESE_ENTRY (region)->src->loop_father; 1516 compute_cloog_iv_types (pc.stmt); 1517 rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free); 1518 newivs_index = htab_create (10, clast_name_index_elt_info, 1519 eq_clast_name_indexes, free); 1520 params_index = htab_create (10, clast_name_index_elt_info, 1521 eq_clast_name_indexes, free); 1522 1523 create_params_index (params_index, pc.prog); 1524 1525 translate_clast (region, context_loop, pc.stmt, 1526 if_region->true_region->entry, 1527 rename_map, &newivs, newivs_index, 1528 bb_pbb_mapping, 1, params_index); 1529 graphite_verify (); 1530 sese_adjust_liveout_phis (region, rename_map, 1531 if_region->region->exit->src, 1532 if_region->false_region->exit, 1533 if_region->true_region->exit); 1534 scev_reset_htab (); 1535 rename_nb_iterations (rename_map); 1536 1537 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++) 1538 rename_sese_parameters (rename_map, SCOP_REGION (scop)); 1539 1540 recompute_all_dominators (); 1541 graphite_verify (); 1542 1543 if (gloog_error) 1544 set_ifsese_condition (if_region, integer_zero_node); 1545 1546 free (if_region->true_region); 1547 free (if_region->region); 1548 free (if_region); 1549 1550 htab_delete (rename_map); 1551 htab_delete (newivs_index); 1552 htab_delete (params_index); 1553 VEC_free (tree, heap, newivs); 1554 cloog_clast_free (pc.stmt); 1555 cloog_program_free (pc.prog); 1556 timevar_pop (TV_GRAPHITE_CODE_GEN); 1557 1558 if (dump_file && (dump_flags & TDF_DETAILS)) 1559 { 1560 loop_p loop; 1561 loop_iterator li; 1562 int num_no_dependency = 0; 1563 1564 FOR_EACH_LOOP (li, loop, 0) 1565 if (loop->can_be_parallel) 1566 num_no_dependency++; 1567 1568 fprintf (dump_file, "\n%d loops carried no dependency.\n", 1569 num_no_dependency); 1570 } 1571 1572 return !gloog_error; 1573} 1574 1575#endif 1576