1/* Translation of ISL AST to Gimple. 2 Copyright (C) 2014-2015 Free Software Foundation, Inc. 3 Contributed by Roman Gareev <gareevroman@gmail.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 23#ifdef HAVE_isl 24#include <isl/constraint.h> 25#include <isl/set.h> 26#include <isl/union_set.h> 27#include <isl/map.h> 28#include <isl/union_map.h> 29#include <isl/ast_build.h> 30 31/* Since ISL-0.13, the extern is in val_gmp.h. */ 32#if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus) 33extern "C" { 34#endif 35#include <isl/val_gmp.h> 36#if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus) 37} 38#endif 39#endif 40 41#include "system.h" 42#include "coretypes.h" 43#include "hash-set.h" 44#include "machmode.h" 45#include "vec.h" 46#include "double-int.h" 47#include "input.h" 48#include "alias.h" 49#include "symtab.h" 50#include "options.h" 51#include "wide-int.h" 52#include "inchash.h" 53#include "tree.h" 54#include "fold-const.h" 55#include "predict.h" 56#include "tm.h" 57#include "hard-reg-set.h" 58#include "input.h" 59#include "function.h" 60#include "dominance.h" 61#include "cfg.h" 62#include "basic-block.h" 63#include "tree-ssa-alias.h" 64#include "internal-fn.h" 65#include "gimple-expr.h" 66#include "is-a.h" 67#include "gimple.h" 68#include "gimple-iterator.h" 69#include "tree-ssa-loop.h" 70#include "tree-pass.h" 71#include "cfgloop.h" 72#include "tree-data-ref.h" 73#include "sese.h" 74#include "tree-ssa-loop-manip.h" 75#include "tree-scalar-evolution.h" 76#include "gimple-ssa.h" 77#include "tree-into-ssa.h" 78#include <map> 79 80#ifdef HAVE_isl 81#include "graphite-poly.h" 82#include "graphite-isl-ast-to-gimple.h" 83 84/* This flag is set when an error occurred during the translation of 85 ISL AST to Gimple. */ 86 87static bool graphite_regenerate_error; 88 89/* We always try to use signed 128 bit types, but fall back to smaller types 90 in case a platform does not provide types of these sizes. In the future we 91 should use isl to derive the optimal type for each subexpression. */ 92 93static int max_mode_int_precision = 94 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0)); 95static int graphite_expression_type_precision = 128 <= max_mode_int_precision ? 96 128 : max_mode_int_precision; 97 98struct ast_build_info 99{ 100 ast_build_info() 101 : is_parallelizable(false) 102 { }; 103 bool is_parallelizable; 104}; 105 106/* Converts a GMP constant VAL to a tree and returns it. */ 107 108static tree 109gmp_cst_to_tree (tree type, mpz_t val) 110{ 111 tree t = type ? type : integer_type_node; 112 mpz_t tmp; 113 114 mpz_init (tmp); 115 mpz_set (tmp, val); 116 wide_int wi = wi::from_mpz (t, tmp, true); 117 mpz_clear (tmp); 118 119 return wide_int_to_tree (t, wi); 120} 121 122/* Verifies properties that GRAPHITE should maintain during translation. */ 123 124static inline void 125graphite_verify (void) 126{ 127#ifdef ENABLE_CHECKING 128 verify_loop_structure (); 129 verify_loop_closed_ssa (true); 130#endif 131} 132 133/* IVS_PARAMS maps ISL's scattering and parameter identifiers 134 to corresponding trees. */ 135 136typedef std::map<isl_id *, tree> ivs_params; 137 138/* Free all memory allocated for ISL's identifiers. */ 139 140void ivs_params_clear (ivs_params &ip) 141{ 142 std::map<isl_id *, tree>::iterator it; 143 for (it = ip.begin (); 144 it != ip.end (); it++) 145 { 146 isl_id_free (it->first); 147 } 148} 149 150static tree 151gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *, 152 ivs_params &ip); 153 154/* Return the tree variable that corresponds to the given isl ast identifier 155 expression (an isl_ast_expr of type isl_ast_expr_id). 156 157 FIXME: We should replace blind conversation of id's type with derivation 158 of the optimal type when we get the corresponding isl support. Blindly 159 converting type sizes may be problematic when we switch to smaller 160 types. */ 161 162static tree 163gcc_expression_from_isl_ast_expr_id (tree type, 164 __isl_keep isl_ast_expr *expr_id, 165 ivs_params &ip) 166{ 167 gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id); 168 isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id); 169 std::map<isl_id *, tree>::iterator res; 170 res = ip.find (tmp_isl_id); 171 isl_id_free (tmp_isl_id); 172 gcc_assert (res != ip.end () && 173 "Could not map isl_id to tree expression"); 174 isl_ast_expr_free (expr_id); 175 return fold_convert (type, res->second); 176} 177 178/* Converts an isl_ast_expr_int expression E to a GCC expression tree of 179 type TYPE. */ 180 181static tree 182gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr) 183{ 184 gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int); 185 isl_val *val = isl_ast_expr_get_val (expr); 186 mpz_t val_mpz_t; 187 mpz_init (val_mpz_t); 188 tree res; 189 if (isl_val_get_num_gmp (val, val_mpz_t) == -1) 190 res = NULL_TREE; 191 else 192 res = gmp_cst_to_tree (type, val_mpz_t); 193 isl_val_free (val); 194 isl_ast_expr_free (expr); 195 mpz_clear (val_mpz_t); 196 return res; 197} 198 199/* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of 200 type TYPE. */ 201 202static tree 203binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) 204{ 205 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); 206 tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip); 207 arg_expr = isl_ast_expr_get_op_arg (expr, 1); 208 tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip); 209 enum isl_ast_op_type expr_type = isl_ast_expr_get_op_type (expr); 210 isl_ast_expr_free (expr); 211 switch (expr_type) 212 { 213 case isl_ast_op_add: 214 return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr); 215 216 case isl_ast_op_sub: 217 return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr); 218 219 case isl_ast_op_mul: 220 return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr); 221 222 case isl_ast_op_div: 223 return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr); 224 225 case isl_ast_op_pdiv_q: 226 return fold_build2 (TRUNC_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr); 227 228 case isl_ast_op_pdiv_r: 229 return fold_build2 (TRUNC_MOD_EXPR, type, tree_lhs_expr, tree_rhs_expr); 230 231 case isl_ast_op_fdiv_q: 232 return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr); 233 234 case isl_ast_op_and: 235 return fold_build2 (TRUTH_ANDIF_EXPR, type, 236 tree_lhs_expr, tree_rhs_expr); 237 238 case isl_ast_op_or: 239 return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr); 240 241 case isl_ast_op_eq: 242 return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr); 243 244 case isl_ast_op_le: 245 return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr); 246 247 case isl_ast_op_lt: 248 return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr); 249 250 case isl_ast_op_ge: 251 return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr); 252 253 case isl_ast_op_gt: 254 return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr); 255 256 default: 257 gcc_unreachable (); 258 } 259} 260 261/* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of 262 type TYPE. */ 263 264static tree 265ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) 266{ 267 gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus); 268 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); 269 tree tree_first_expr 270 = gcc_expression_from_isl_expression (type, arg_expr, ip); 271 arg_expr = isl_ast_expr_get_op_arg (expr, 1); 272 tree tree_second_expr 273 = gcc_expression_from_isl_expression (type, arg_expr, ip); 274 arg_expr = isl_ast_expr_get_op_arg (expr, 2); 275 tree tree_third_expr 276 = gcc_expression_from_isl_expression (type, arg_expr, ip); 277 isl_ast_expr_free (expr); 278 return fold_build3 (COND_EXPR, type, tree_first_expr, 279 tree_second_expr, tree_third_expr); 280} 281 282/* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of 283 type TYPE. */ 284 285static tree 286unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) 287{ 288 gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus); 289 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); 290 tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip); 291 isl_ast_expr_free (expr); 292 return fold_build1 (NEGATE_EXPR, type, tree_expr); 293} 294 295/* Converts an isl_ast_expr_op expression E with unknown number of arguments 296 to a GCC expression tree of type TYPE. */ 297 298static tree 299nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) 300{ 301 enum tree_code op_code; 302 switch (isl_ast_expr_get_op_type (expr)) 303 { 304 case isl_ast_op_max: 305 op_code = MAX_EXPR; 306 break; 307 308 case isl_ast_op_min: 309 op_code = MIN_EXPR; 310 break; 311 312 default: 313 gcc_unreachable (); 314 } 315 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); 316 tree res = gcc_expression_from_isl_expression (type, arg_expr, ip); 317 int i; 318 for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++) 319 { 320 arg_expr = isl_ast_expr_get_op_arg (expr, i); 321 tree t = gcc_expression_from_isl_expression (type, arg_expr, ip); 322 res = fold_build2 (op_code, type, res, t); 323 } 324 isl_ast_expr_free (expr); 325 return res; 326} 327 328 329/* Converts an isl_ast_expr_op expression E to a GCC expression tree of 330 type TYPE. */ 331 332static tree 333gcc_expression_from_isl_expr_op (tree type, __isl_take isl_ast_expr *expr, 334 ivs_params &ip) 335{ 336 gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op); 337 switch (isl_ast_expr_get_op_type (expr)) 338 { 339 /* These isl ast expressions are not supported yet. */ 340 case isl_ast_op_error: 341 case isl_ast_op_call: 342 case isl_ast_op_and_then: 343 case isl_ast_op_or_else: 344 case isl_ast_op_select: 345 gcc_unreachable (); 346 347 case isl_ast_op_max: 348 case isl_ast_op_min: 349 return nary_op_to_tree (type, expr, ip); 350 351 case isl_ast_op_add: 352 case isl_ast_op_sub: 353 case isl_ast_op_mul: 354 case isl_ast_op_div: 355 case isl_ast_op_pdiv_q: 356 case isl_ast_op_pdiv_r: 357 case isl_ast_op_fdiv_q: 358 case isl_ast_op_and: 359 case isl_ast_op_or: 360 case isl_ast_op_eq: 361 case isl_ast_op_le: 362 case isl_ast_op_lt: 363 case isl_ast_op_ge: 364 case isl_ast_op_gt: 365 return binary_op_to_tree (type, expr, ip); 366 367 case isl_ast_op_minus: 368 return unary_op_to_tree (type, expr, ip); 369 370 case isl_ast_op_cond: 371 return ternary_op_to_tree (type, expr, ip); 372 373 default: 374 gcc_unreachable (); 375 } 376 377 return NULL_TREE; 378} 379 380/* Converts an ISL AST expression E back to a GCC expression tree of 381 type TYPE. */ 382 383static tree 384gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *expr, 385 ivs_params &ip) 386{ 387 switch (isl_ast_expr_get_type (expr)) 388 { 389 case isl_ast_expr_id: 390 return gcc_expression_from_isl_ast_expr_id (type, expr, ip); 391 392 case isl_ast_expr_int: 393 return gcc_expression_from_isl_expr_int (type, expr); 394 395 case isl_ast_expr_op: 396 return gcc_expression_from_isl_expr_op (type, expr, ip); 397 398 default: 399 gcc_unreachable (); 400 } 401 402 return NULL_TREE; 403} 404 405/* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an 406 induction variable for the new LOOP. New LOOP is attached to CFG 407 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and 408 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds 409 ISL's scattering name to the induction variable created for the 410 loop of STMT. The new induction variable is inserted in the NEWIVS 411 vector and is of type TYPE. */ 412 413static struct loop * 414graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for, 415 loop_p outer, tree type, tree lb, tree ub, 416 ivs_params &ip) 417{ 418 isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for); 419 tree stride = gcc_expression_from_isl_expression (type, for_inc, ip); 420 tree ivvar = create_tmp_var (type, "graphite_IV"); 421 tree iv, iv_after_increment; 422 loop_p loop = create_empty_loop_on_edge 423 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment, 424 outer ? outer : entry_edge->src->loop_father); 425 426 isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for); 427 isl_id *id = isl_ast_expr_get_id (for_iterator); 428 std::map<isl_id *, tree>::iterator res; 429 res = ip.find (id); 430 if (ip.count (id)) 431 isl_id_free (res->first); 432 ip[id] = iv; 433 isl_ast_expr_free (for_iterator); 434 return loop; 435} 436 437static edge 438translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node, 439 edge next_e, ivs_params &ip); 440 441/* Create the loop for a isl_ast_node_for. 442 443 - NEXT_E is the edge where new generated code should be attached. */ 444 445static edge 446translate_isl_ast_for_loop (loop_p context_loop, 447 __isl_keep isl_ast_node *node_for, edge next_e, 448 tree type, tree lb, tree ub, 449 ivs_params &ip) 450{ 451 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for); 452 struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop, 453 type, lb, ub, ip); 454 edge last_e = single_exit (loop); 455 edge to_body = single_succ_edge (loop->header); 456 basic_block after = to_body->dest; 457 458 /* Create a basic block for loop close phi nodes. */ 459 last_e = single_succ_edge (split_edge (last_e)); 460 461 /* Translate the body of the loop. */ 462 isl_ast_node *for_body = isl_ast_node_for_get_body (node_for); 463 next_e = translate_isl_ast (loop, for_body, to_body, ip); 464 isl_ast_node_free (for_body); 465 redirect_edge_succ_nodup (next_e, after); 466 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src); 467 468 if (flag_loop_parallelize_all) 469 { 470 isl_id *id = isl_ast_node_get_annotation (node_for); 471 gcc_assert (id); 472 ast_build_info *for_info = (ast_build_info *) isl_id_get_user (id); 473 loop->can_be_parallel = for_info->is_parallelizable; 474 free (for_info); 475 isl_id_free (id); 476 } 477 478 return last_e; 479} 480 481/* We use this function to get the upper bound because of the form, 482 which is used by isl to represent loops: 483 484 for (iterator = init; cond; iterator += inc) 485 486 { 487 488 ... 489 490 } 491 492 The loop condition is an arbitrary expression, which contains the 493 current loop iterator. 494 495 (e.g. iterator + 3 < B && C > iterator + A) 496 497 We have to know the upper bound of the iterator to generate a loop 498 in Gimple form. It can be obtained from the special representation 499 of the loop condition, which is generated by isl, 500 if the ast_build_atomic_upper_bound option is set. In this case, 501 isl generates a loop condition that consists of the current loop 502 iterator, + an operator (< or <=) and an expression not involving 503 the iterator, which is processed and returned by this function. 504 505 (e.g iterator <= upper-bound-expression-without-iterator) */ 506 507static __isl_give isl_ast_expr * 508get_upper_bound (__isl_keep isl_ast_node *node_for) 509{ 510 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for); 511 isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for); 512 gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op); 513 isl_ast_expr *res; 514 switch (isl_ast_expr_get_op_type (for_cond)) 515 { 516 case isl_ast_op_le: 517 res = isl_ast_expr_get_op_arg (for_cond, 1); 518 break; 519 520 case isl_ast_op_lt: 521 { 522 // (iterator < ub) => (iterator <= ub - 1) 523 isl_val *one = 524 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1); 525 isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1); 526 res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one)); 527 break; 528 } 529 530 default: 531 gcc_unreachable (); 532 } 533 isl_ast_expr_free (for_cond); 534 return res; 535} 536 537/* All loops generated by create_empty_loop_on_edge have the form of 538 a post-test loop: 539 540 do 541 542 { 543 body of the loop; 544 } while (lower bound < upper bound); 545 546 We create a new if region protecting the loop to be executed, if 547 the execution count is zero (lower bound > upper bound). */ 548 549static edge 550graphite_create_new_loop_guard (edge entry_edge, 551 __isl_keep isl_ast_node *node_for, tree *type, 552 tree *lb, tree *ub, ivs_params &ip) 553{ 554 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for); 555 tree cond_expr; 556 edge exit_edge; 557 558 *type = 559 build_nonstandard_integer_type (graphite_expression_type_precision, 0); 560 isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for); 561 *lb = gcc_expression_from_isl_expression (*type, for_init, ip); 562 isl_ast_expr *upper_bound = get_upper_bound (node_for); 563 *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip); 564 565 /* When ub is simply a constant or a parameter, use lb <= ub. */ 566 if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME) 567 cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub); 568 else 569 { 570 tree one = (POINTER_TYPE_P (*type) 571 ? convert_to_ptrofftype (integer_one_node) 572 : fold_convert (*type, integer_one_node)); 573 /* Adding +1 and using LT_EXPR helps with loop latches that have a 574 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this 575 becomes 2^k-1 due to integer overflow, and the condition lb <= ub 576 is true, even if we do not want this. However lb < ub + 1 is false, 577 as expected. */ 578 tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR 579 : PLUS_EXPR, *type, *ub, one); 580 581 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one); 582 } 583 584 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); 585 586 return exit_edge; 587} 588 589/* Translates an isl_ast_node_for to Gimple. */ 590 591static edge 592translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node, 593 edge next_e, ivs_params &ip) 594{ 595 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for); 596 tree type, lb, ub; 597 edge last_e = graphite_create_new_loop_guard (next_e, node, &type, 598 &lb, &ub, ip); 599 edge true_e = get_true_edge_from_guard_bb (next_e->dest); 600 601 translate_isl_ast_for_loop (context_loop, node, true_e, 602 type, lb, ub, ip); 603 return last_e; 604} 605 606/* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction 607 variables of the loops around GBB in SESE. 608 609 FIXME: Instead of using a vec<tree> that maps each loop id to a possible 610 chrec, we could consider using a map<int, tree> that maps loop ids to the 611 corresponding tree expressions. */ 612 613static void 614build_iv_mapping (vec<tree> iv_map, gimple_bb_p gbb, 615 __isl_keep isl_ast_expr *user_expr, ivs_params &ip, 616 sese region) 617{ 618 gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op && 619 isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call); 620 int i; 621 isl_ast_expr *arg_expr; 622 for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++) 623 { 624 arg_expr = isl_ast_expr_get_op_arg (user_expr, i); 625 tree type = 626 build_nonstandard_integer_type (graphite_expression_type_precision, 0); 627 tree t = gcc_expression_from_isl_expression (type, arg_expr, ip); 628 loop_p old_loop = gbb_loop_at_index (gbb, region, i - 1); 629 iv_map[old_loop->num] = t; 630 } 631 632} 633 634/* Translates an isl_ast_node_user to Gimple. 635 636 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */ 637 638static edge 639translate_isl_ast_node_user (__isl_keep isl_ast_node *node, 640 edge next_e, ivs_params &ip) 641{ 642 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user); 643 isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node); 644 isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0); 645 gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id); 646 isl_id *name_id = isl_ast_expr_get_id (name_expr); 647 poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id); 648 gcc_assert (pbb); 649 gimple_bb_p gbb = PBB_BLACK_BOX (pbb); 650 vec<tree> iv_map; 651 isl_ast_expr_free (name_expr); 652 isl_id_free (name_id); 653 654 gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) && 655 "The entry block should not even appear within a scop"); 656 657 int nb_loops = number_of_loops (cfun); 658 iv_map.create (nb_loops); 659 iv_map.safe_grow_cleared (nb_loops); 660 661 build_iv_mapping (iv_map, gbb, user_expr, ip, SCOP_REGION (pbb->scop)); 662 isl_ast_expr_free (user_expr); 663 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), 664 SCOP_REGION (pbb->scop), next_e, 665 iv_map, 666 &graphite_regenerate_error); 667 iv_map.release (); 668 mark_virtual_operands_for_renaming (cfun); 669 update_ssa (TODO_update_ssa); 670 return next_e; 671} 672 673/* Translates an isl_ast_node_block to Gimple. */ 674 675static edge 676translate_isl_ast_node_block (loop_p context_loop, 677 __isl_keep isl_ast_node *node, 678 edge next_e, ivs_params &ip) 679{ 680 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_block); 681 isl_ast_node_list *node_list = isl_ast_node_block_get_children (node); 682 int i; 683 for (i = 0; i < isl_ast_node_list_n_ast_node (node_list); i++) 684 { 685 isl_ast_node *tmp_node = isl_ast_node_list_get_ast_node (node_list, i); 686 next_e = translate_isl_ast (context_loop, tmp_node, next_e, ip); 687 isl_ast_node_free (tmp_node); 688 } 689 isl_ast_node_list_free (node_list); 690 return next_e; 691} 692 693/* Creates a new if region corresponding to ISL's cond. */ 694 695static edge 696graphite_create_new_guard (edge entry_edge, __isl_take isl_ast_expr *if_cond, 697 ivs_params &ip) 698{ 699 tree type = 700 build_nonstandard_integer_type (graphite_expression_type_precision, 0); 701 tree cond_expr = gcc_expression_from_isl_expression (type, if_cond, ip); 702 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); 703 return exit_edge; 704} 705 706/* Translates an isl_ast_node_if to Gimple. */ 707 708static edge 709translate_isl_ast_node_if (loop_p context_loop, 710 __isl_keep isl_ast_node *node, 711 edge next_e, ivs_params &ip) 712{ 713 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_if); 714 isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node); 715 edge last_e = graphite_create_new_guard (next_e, if_cond, ip); 716 717 edge true_e = get_true_edge_from_guard_bb (next_e->dest); 718 isl_ast_node *then_node = isl_ast_node_if_get_then (node); 719 translate_isl_ast (context_loop, then_node, true_e, ip); 720 isl_ast_node_free (then_node); 721 722 edge false_e = get_false_edge_from_guard_bb (next_e->dest); 723 isl_ast_node *else_node = isl_ast_node_if_get_else (node); 724 if (isl_ast_node_get_type (else_node) != isl_ast_node_error) 725 translate_isl_ast (context_loop, else_node, false_e, ip); 726 isl_ast_node_free (else_node); 727 return last_e; 728} 729 730/* Translates an ISL AST node NODE to GCC representation in the 731 context of a SESE. */ 732 733static edge 734translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node, 735 edge next_e, ivs_params &ip) 736{ 737 switch (isl_ast_node_get_type (node)) 738 { 739 case isl_ast_node_error: 740 gcc_unreachable (); 741 742 case isl_ast_node_for: 743 return translate_isl_ast_node_for (context_loop, node, 744 next_e, ip); 745 746 case isl_ast_node_if: 747 return translate_isl_ast_node_if (context_loop, node, 748 next_e, ip); 749 750 case isl_ast_node_user: 751 return translate_isl_ast_node_user (node, next_e, ip); 752 753 case isl_ast_node_block: 754 return translate_isl_ast_node_block (context_loop, node, 755 next_e, ip); 756 757 default: 758 gcc_unreachable (); 759 } 760} 761 762/* Prints NODE to FILE. */ 763 764void 765print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node, 766 __isl_keep isl_ctx *ctx) 767{ 768 isl_printer *prn = isl_printer_to_file (ctx, file); 769 prn = isl_printer_set_output_format (prn, ISL_FORMAT_C); 770 prn = isl_printer_print_ast_node (prn, node); 771 prn = isl_printer_print_str (prn, "\n"); 772 isl_printer_free (prn); 773} 774 775/* Add ISL's parameter identifiers and corresponding.trees to ivs_params */ 776 777static void 778add_parameters_to_ivs_params (scop_p scop, ivs_params &ip) 779{ 780 sese region = SCOP_REGION (scop); 781 unsigned nb_parameters = isl_set_dim (scop->context, isl_dim_param); 782 gcc_assert (nb_parameters == SESE_PARAMS (region).length ()); 783 unsigned i; 784 for (i = 0; i < nb_parameters; i++) 785 { 786 isl_id *tmp_id = isl_set_get_dim_id (scop->context, isl_dim_param, i); 787 ip[tmp_id] = SESE_PARAMS (region)[i]; 788 } 789} 790 791 792/* Generates a build, which specifies the constraints on the parameters. */ 793 794static __isl_give isl_ast_build * 795generate_isl_context (scop_p scop) 796{ 797 isl_set *context_isl = isl_set_params (isl_set_copy (scop->context)); 798 return isl_ast_build_from_context (context_isl); 799} 800 801/* Get the maximal number of schedule dimensions in the scop SCOP. */ 802 803static 804int get_max_schedule_dimensions (scop_p scop) 805{ 806 int i; 807 poly_bb_p pbb; 808 int schedule_dims = 0; 809 810 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) 811 { 812 int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out); 813 if (pbb_schedule_dims > schedule_dims) 814 schedule_dims = pbb_schedule_dims; 815 } 816 817 return schedule_dims; 818} 819 820/* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions. 821 822 For schedules with different dimensionality, the isl AST generator can not 823 define an order and will just randomly choose an order. The solution to this 824 problem is to extend all schedules to the maximal number of schedule 825 dimensions (using '0's for the remaining values). */ 826 827static __isl_give isl_map * 828extend_schedule (__isl_take isl_map *schedule, int nb_schedule_dims) 829{ 830 int tmp_dims = isl_map_dim (schedule, isl_dim_out); 831 schedule = 832 isl_map_add_dims (schedule, isl_dim_out, nb_schedule_dims - tmp_dims); 833 isl_val *zero = 834 isl_val_int_from_si (isl_map_get_ctx (schedule), 0); 835 int i; 836 for (i = tmp_dims; i < nb_schedule_dims; i++) 837 { 838 schedule = 839 isl_map_fix_val (schedule, isl_dim_out, i, isl_val_copy (zero)); 840 } 841 isl_val_free (zero); 842 return schedule; 843} 844 845/* Set the separation_class option for unroll and jam. */ 846 847static __isl_give isl_union_map * 848generate_luj_sepclass_opt (scop_p scop, __isl_take isl_union_set *domain, 849 int dim, int cl) 850{ 851 isl_map *map; 852 isl_space *space, *space_sep; 853 isl_ctx *ctx; 854 isl_union_map *mapu; 855 int nsched = get_max_schedule_dimensions (scop); 856 857 ctx = scop->ctx; 858 space_sep = isl_space_alloc (ctx, 0, 1, 1); 859 space_sep = isl_space_wrap (space_sep); 860 space_sep = isl_space_set_tuple_name (space_sep, isl_dim_set, 861 "separation_class"); 862 space = isl_set_get_space (scop->context); 863 space_sep = isl_space_align_params (space_sep, isl_space_copy(space)); 864 space = isl_space_map_from_domain_and_range (space, space_sep); 865 space = isl_space_add_dims (space,isl_dim_in, nsched); 866 map = isl_map_universe (space); 867 isl_map_fix_si (map,isl_dim_out,0,dim); 868 isl_map_fix_si (map,isl_dim_out,1,cl); 869 870 mapu = isl_union_map_intersect_domain (isl_union_map_from_map (map), 871 domain); 872 return (mapu); 873} 874 875/* Compute the separation class for loop unroll and jam. */ 876 877static __isl_give isl_union_set * 878generate_luj_sepclass (scop_p scop) 879{ 880 int i; 881 poly_bb_p pbb; 882 isl_union_set *domain_isl; 883 884 domain_isl = isl_union_set_empty (isl_set_get_space (scop->context)); 885 886 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) 887 { 888 isl_set *bb_domain; 889 isl_set *bb_domain_s; 890 891 if (pbb->map_sepclass == NULL) 892 continue; 893 894 if (isl_set_is_empty (pbb->domain)) 895 continue; 896 897 bb_domain = isl_set_copy (pbb->domain); 898 bb_domain_s = isl_set_apply (bb_domain, pbb->map_sepclass); 899 pbb->map_sepclass = NULL; 900 901 domain_isl = 902 isl_union_set_union (domain_isl, isl_union_set_from_set (bb_domain_s)); 903 } 904 905 return domain_isl; 906} 907 908/* Set the AST built options for loop unroll and jam. */ 909 910static __isl_give isl_union_map * 911generate_luj_options (scop_p scop) 912{ 913 isl_union_set *domain_isl; 914 isl_union_map *options_isl_ss; 915 isl_union_map *options_isl = 916 isl_union_map_empty (isl_set_get_space (scop->context)); 917 int dim = get_max_schedule_dimensions (scop) - 1; 918 int dim1 = dim - PARAM_VALUE (PARAM_LOOP_UNROLL_JAM_DEPTH); 919 920 if (!flag_loop_unroll_jam) 921 return options_isl; 922 923 domain_isl = generate_luj_sepclass (scop); 924 925 options_isl_ss = generate_luj_sepclass_opt (scop, domain_isl, dim1, 0); 926 options_isl = isl_union_map_union (options_isl, options_isl_ss); 927 928 return options_isl; 929} 930 931/* Generates a schedule, which specifies an order used to 932 visit elements in a domain. */ 933 934static __isl_give isl_union_map * 935generate_isl_schedule (scop_p scop) 936{ 937 int nb_schedule_dims = get_max_schedule_dimensions (scop); 938 int i; 939 poly_bb_p pbb; 940 isl_union_map *schedule_isl = 941 isl_union_map_empty (isl_set_get_space (scop->context)); 942 943 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) 944 { 945 /* Dead code elimination: when the domain of a PBB is empty, 946 don't generate code for the PBB. */ 947 if (isl_set_is_empty (pbb->domain)) 948 continue; 949 950 isl_map *bb_schedule = isl_map_copy (pbb->transformed); 951 bb_schedule = isl_map_intersect_domain (bb_schedule, 952 isl_set_copy (pbb->domain)); 953 bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims); 954 schedule_isl = 955 isl_union_map_union (schedule_isl, 956 isl_union_map_from_map (bb_schedule)); 957 } 958 return schedule_isl; 959} 960 961/* This method is executed before the construction of a for node. */ 962static __isl_give isl_id * 963ast_build_before_for (__isl_keep isl_ast_build *build, void *user) 964{ 965 isl_union_map *dependences = (isl_union_map *) user; 966 ast_build_info *for_info = XNEW (struct ast_build_info); 967 isl_union_map *schedule = isl_ast_build_get_schedule (build); 968 isl_space *schedule_space = isl_ast_build_get_schedule_space (build); 969 int dimension = isl_space_dim (schedule_space, isl_dim_out); 970 for_info->is_parallelizable = 971 !carries_deps (schedule, dependences, dimension); 972 isl_union_map_free (schedule); 973 isl_space_free (schedule_space); 974 isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info); 975 return id; 976} 977 978/* Set the separate option for all dimensions. 979 This helps to reduce control overhead. 980 Set the options for unroll and jam. */ 981 982static __isl_give isl_ast_build * 983set_options (__isl_take isl_ast_build *control, 984 __isl_keep isl_union_map *schedule, 985 __isl_take isl_union_map *opt_luj) 986{ 987 isl_ctx *ctx = isl_union_map_get_ctx (schedule); 988 isl_space *range_space = isl_space_set_alloc (ctx, 0, 1); 989 range_space = 990 isl_space_set_tuple_name (range_space, isl_dim_set, "separate"); 991 isl_union_set *range = 992 isl_union_set_from_set (isl_set_universe (range_space)); 993 isl_union_set *domain = isl_union_map_range (isl_union_map_copy (schedule)); 994 domain = isl_union_set_universe (domain); 995 isl_union_map *options = isl_union_map_from_domain_and_range (domain, range); 996 997 options = isl_union_map_union (options, opt_luj); 998 999 return isl_ast_build_set_options (control, options); 1000} 1001 1002static __isl_give isl_ast_node * 1003scop_to_isl_ast (scop_p scop, ivs_params &ip) 1004{ 1005 /* Generate loop upper bounds that consist of the current loop iterator, 1006 an operator (< or <=) and an expression not involving the iterator. 1007 If this option is not set, then the current loop iterator may appear several 1008 times in the upper bound. See the isl manual for more details. */ 1009 isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true); 1010 1011 add_parameters_to_ivs_params (scop, ip); 1012 1013 isl_union_map *options_luj = generate_luj_options (scop); 1014 1015 isl_union_map *schedule_isl = generate_isl_schedule (scop); 1016 isl_ast_build *context_isl = generate_isl_context (scop); 1017 1018 context_isl = set_options (context_isl, schedule_isl, options_luj); 1019 1020 isl_union_map *dependences = NULL; 1021 if (flag_loop_parallelize_all) 1022 { 1023 dependences = scop_get_dependences (scop); 1024 context_isl = 1025 isl_ast_build_set_before_each_for (context_isl, ast_build_before_for, 1026 dependences); 1027 } 1028 isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl, 1029 schedule_isl); 1030 if(dependences) 1031 isl_union_map_free (dependences); 1032 isl_ast_build_free (context_isl); 1033 return ast_isl; 1034} 1035 1036/* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for 1037 the given SCOP. Return true if code generation succeeded. 1038 1039 FIXME: This is not yet a full implementation of the code generator 1040 with ISL ASTs. Generation of GIMPLE code has to be completed. */ 1041 1042bool 1043graphite_regenerate_ast_isl (scop_p scop) 1044{ 1045 loop_p context_loop; 1046 sese region = SCOP_REGION (scop); 1047 ifsese if_region = NULL; 1048 isl_ast_node *root_node; 1049 ivs_params ip; 1050 1051 timevar_push (TV_GRAPHITE_CODE_GEN); 1052 graphite_regenerate_error = false; 1053 root_node = scop_to_isl_ast (scop, ip); 1054 1055 if (dump_file && (dump_flags & TDF_DETAILS)) 1056 { 1057 fprintf (dump_file, "\nISL AST generated by ISL: \n"); 1058 print_isl_ast_node (dump_file, root_node, scop->ctx); 1059 fprintf (dump_file, "\n"); 1060 } 1061 1062 recompute_all_dominators (); 1063 graphite_verify (); 1064 1065 if_region = move_sese_in_condition (region); 1066 sese_insert_phis_for_liveouts (region, 1067 if_region->region->exit->src, 1068 if_region->false_region->exit, 1069 if_region->true_region->exit); 1070 recompute_all_dominators (); 1071 graphite_verify (); 1072 1073 context_loop = SESE_ENTRY (region)->src->loop_father; 1074 1075 translate_isl_ast (context_loop, root_node, if_region->true_region->entry, 1076 ip); 1077 graphite_verify (); 1078 scev_reset (); 1079 recompute_all_dominators (); 1080 graphite_verify (); 1081 1082 if (graphite_regenerate_error) 1083 set_ifsese_condition (if_region, integer_zero_node); 1084 1085 free (if_region->true_region); 1086 free (if_region->region); 1087 free (if_region); 1088 1089 ivs_params_clear (ip); 1090 isl_ast_node_free (root_node); 1091 timevar_pop (TV_GRAPHITE_CODE_GEN); 1092 1093 if (dump_file && (dump_flags & TDF_DETAILS)) 1094 { 1095 loop_p loop; 1096 int num_no_dependency = 0; 1097 1098 FOR_EACH_LOOP (loop, 0) 1099 if (loop->can_be_parallel) 1100 num_no_dependency++; 1101 1102 fprintf (dump_file, "\n%d loops carried no dependency.\n", 1103 num_no_dependency); 1104 } 1105 1106 return !graphite_regenerate_error; 1107} 1108#endif 1109