1/* Conversion of SESE regions to Polyhedra. 2 Copyright (C) 2009-2022 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#define INCLUDE_ISL 22 23#include "config.h" 24 25#ifdef HAVE_isl 26 27#include "system.h" 28#include "coretypes.h" 29#include "backend.h" 30#include "cfghooks.h" 31#include "tree.h" 32#include "gimple.h" 33#include "ssa.h" 34#include "fold-const.h" 35#include "gimple-iterator.h" 36#include "gimplify.h" 37#include "gimplify-me.h" 38#include "tree-cfg.h" 39#include "tree-ssa-loop-manip.h" 40#include "tree-ssa-loop-niter.h" 41#include "tree-ssa-loop.h" 42#include "tree-into-ssa.h" 43#include "tree-pass.h" 44#include "cfgloop.h" 45#include "tree-data-ref.h" 46#include "tree-scalar-evolution.h" 47#include "domwalk.h" 48#include "tree-ssa-propagate.h" 49#include "graphite.h" 50 51/* Return an isl identifier for the polyhedral basic block PBB. */ 52 53static isl_id * 54isl_id_for_pbb (scop_p s, poly_bb_p pbb) 55{ 56 char name[14]; 57 snprintf (name, sizeof (name), "S_%d", pbb_index (pbb)); 58 return isl_id_alloc (s->isl_context, name, pbb); 59} 60 61static isl_pw_aff *extract_affine (scop_p, tree, __isl_take isl_space *space); 62 63/* Extract an affine expression from the chain of recurrence E. */ 64 65static isl_pw_aff * 66extract_affine_chrec (scop_p s, tree e, __isl_take isl_space *space) 67{ 68 isl_pw_aff *lhs = extract_affine (s, CHREC_LEFT (e), isl_space_copy (space)); 69 isl_pw_aff *rhs = extract_affine (s, CHREC_RIGHT (e), isl_space_copy (space)); 70 isl_local_space *ls = isl_local_space_from_space (space); 71 unsigned pos = sese_loop_depth (s->scop_info->region, get_chrec_loop (e)) - 1; 72 isl_aff *loop = isl_aff_set_coefficient_si 73 (isl_aff_zero_on_domain (ls), isl_dim_in, pos, 1); 74 isl_pw_aff *l = isl_pw_aff_from_aff (loop); 75 76 /* Before multiplying, make sure that the result is affine. */ 77 gcc_assert (isl_pw_aff_is_cst (rhs) 78 || isl_pw_aff_is_cst (l)); 79 80 return isl_pw_aff_add (lhs, isl_pw_aff_mul (rhs, l)); 81} 82 83/* Extract an affine expression from the mult_expr E. */ 84 85static isl_pw_aff * 86extract_affine_mul (scop_p s, tree e, __isl_take isl_space *space) 87{ 88 isl_pw_aff *lhs = extract_affine (s, TREE_OPERAND (e, 0), 89 isl_space_copy (space)); 90 isl_pw_aff *rhs = extract_affine (s, TREE_OPERAND (e, 1), space); 91 92 if (!isl_pw_aff_is_cst (lhs) 93 && !isl_pw_aff_is_cst (rhs)) 94 { 95 isl_pw_aff_free (lhs); 96 isl_pw_aff_free (rhs); 97 return NULL; 98 } 99 100 return isl_pw_aff_mul (lhs, rhs); 101} 102 103/* Return an isl identifier from the name of the ssa_name E. */ 104 105static isl_id * 106isl_id_for_ssa_name (scop_p s, tree e) 107{ 108 char name1[14]; 109 snprintf (name1, sizeof (name1), "P_%d", SSA_NAME_VERSION (e)); 110 return isl_id_alloc (s->isl_context, name1, e); 111} 112 113/* Return an isl identifier for the data reference DR. Data references and 114 scalar references get the same isl_id. They need to be comparable and are 115 distinguished through the first dimension, which contains the alias set or 116 SSA_NAME_VERSION number. */ 117 118static isl_id * 119isl_id_for_dr (scop_p s) 120{ 121 return isl_id_alloc (s->isl_context, "", 0); 122} 123 124/* Extract an affine expression from the ssa_name E. */ 125 126static isl_pw_aff * 127extract_affine_name (int dimension, __isl_take isl_space *space) 128{ 129 isl_set *dom = isl_set_universe (isl_space_copy (space)); 130 isl_aff *aff = isl_aff_zero_on_domain (isl_local_space_from_space (space)); 131 aff = isl_aff_add_coefficient_si (aff, isl_dim_param, dimension, 1); 132 return isl_pw_aff_alloc (dom, aff); 133} 134 135/* Convert WI to a isl_val with CTX. */ 136 137static __isl_give isl_val * 138isl_val_int_from_wi (isl_ctx *ctx, const widest_int &wi) 139{ 140 if (wi::neg_p (wi, SIGNED)) 141 { 142 widest_int mwi = -wi; 143 return isl_val_neg (isl_val_int_from_chunks (ctx, mwi.get_len (), 144 sizeof (HOST_WIDE_INT), 145 mwi.get_val ())); 146 } 147 return isl_val_int_from_chunks (ctx, wi.get_len (), sizeof (HOST_WIDE_INT), 148 wi.get_val ()); 149} 150 151/* Extract an affine expression from the gmp constant G. */ 152 153static isl_pw_aff * 154extract_affine_wi (const widest_int &g, __isl_take isl_space *space) 155{ 156 isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space)); 157 isl_aff *aff = isl_aff_zero_on_domain (ls); 158 isl_set *dom = isl_set_universe (space); 159 isl_ctx *ct = isl_aff_get_ctx (aff); 160 isl_val *v = isl_val_int_from_wi (ct, g); 161 aff = isl_aff_add_constant_val (aff, v); 162 163 return isl_pw_aff_alloc (dom, aff); 164} 165 166/* Extract an affine expression from the integer_cst E. */ 167 168static isl_pw_aff * 169extract_affine_int (tree e, __isl_take isl_space *space) 170{ 171 isl_pw_aff *res = extract_affine_wi (wi::to_widest (e), space); 172 return res; 173} 174 175/* Compute pwaff mod 2^width. */ 176 177static isl_pw_aff * 178wrap (isl_pw_aff *pwaff, unsigned width) 179{ 180 isl_val *mod; 181 182 mod = isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff), width); 183 mod = isl_val_2exp (mod); 184 pwaff = isl_pw_aff_mod_val (pwaff, mod); 185 186 return pwaff; 187} 188 189/* When parameter NAME is in REGION, returns its index in SESE_PARAMS. 190 Otherwise returns -1. */ 191 192static inline int 193parameter_index_in_region (tree name, sese_info_p region) 194{ 195 int i; 196 tree p; 197 FOR_EACH_VEC_ELT (region->params, i, p) 198 if (p == name) 199 return i; 200 return -1; 201} 202 203/* Extract an affine expression from the tree E in the scop S. */ 204 205static isl_pw_aff * 206extract_affine (scop_p s, tree e, __isl_take isl_space *space) 207{ 208 isl_pw_aff *lhs, *rhs, *res; 209 210 if (e == chrec_dont_know) { 211 isl_space_free (space); 212 return NULL; 213 } 214 215 tree type = TREE_TYPE (e); 216 switch (TREE_CODE (e)) 217 { 218 case POLYNOMIAL_CHREC: 219 res = extract_affine_chrec (s, e, space); 220 break; 221 222 case MULT_EXPR: 223 res = extract_affine_mul (s, e, space); 224 break; 225 226 case POINTER_PLUS_EXPR: 227 { 228 lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); 229 /* The RHS of a pointer-plus expression is to be interpreted 230 as signed value. Try to look through a sign-changing conversion 231 first. */ 232 tree tem = TREE_OPERAND (e, 1); 233 STRIP_NOPS (tem); 234 rhs = extract_affine (s, tem, space); 235 if (TYPE_UNSIGNED (TREE_TYPE (tem))) 236 rhs = wrap (rhs, TYPE_PRECISION (type) - 1); 237 res = isl_pw_aff_add (lhs, rhs); 238 break; 239 } 240 241 case PLUS_EXPR: 242 lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); 243 rhs = extract_affine (s, TREE_OPERAND (e, 1), space); 244 res = isl_pw_aff_add (lhs, rhs); 245 break; 246 247 case MINUS_EXPR: 248 lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); 249 rhs = extract_affine (s, TREE_OPERAND (e, 1), space); 250 res = isl_pw_aff_sub (lhs, rhs); 251 break; 252 253 case BIT_NOT_EXPR: 254 lhs = extract_affine (s, integer_minus_one_node, isl_space_copy (space)); 255 rhs = extract_affine (s, TREE_OPERAND (e, 0), space); 256 res = isl_pw_aff_sub (lhs, rhs); 257 /* We need to always wrap the result of a bitwise operation. */ 258 return wrap (res, TYPE_PRECISION (type) - (TYPE_UNSIGNED (type) ? 0 : 1)); 259 260 case NEGATE_EXPR: 261 lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); 262 rhs = extract_affine (s, integer_minus_one_node, space); 263 res = isl_pw_aff_mul (lhs, rhs); 264 break; 265 266 case SSA_NAME: 267 { 268 gcc_assert (! defined_in_sese_p (e, s->scop_info->region)); 269 int dim = parameter_index_in_region (e, s->scop_info); 270 gcc_assert (dim != -1); 271 /* No need to wrap a parameter. */ 272 return extract_affine_name (dim, space); 273 } 274 275 case INTEGER_CST: 276 res = extract_affine_int (e, space); 277 /* No need to wrap a single integer. */ 278 return res; 279 280 CASE_CONVERT: 281 { 282 tree itype = TREE_TYPE (TREE_OPERAND (e, 0)); 283 res = extract_affine (s, TREE_OPERAND (e, 0), space); 284 /* Signed values, even if overflow is undefined, get modulo-reduced. 285 But only if not all values of the old type fit in the new. */ 286 if (! TYPE_UNSIGNED (type) 287 && ((TYPE_UNSIGNED (itype) 288 && TYPE_PRECISION (type) <= TYPE_PRECISION (itype)) 289 || TYPE_PRECISION (type) < TYPE_PRECISION (itype))) 290 res = wrap (res, TYPE_PRECISION (type) - 1); 291 else if (TYPE_UNSIGNED (type) 292 && (!TYPE_UNSIGNED (itype) 293 || TYPE_PRECISION (type) < TYPE_PRECISION (itype))) 294 res = wrap (res, TYPE_PRECISION (type)); 295 return res; 296 } 297 298 case NON_LVALUE_EXPR: 299 res = extract_affine (s, TREE_OPERAND (e, 0), space); 300 break; 301 302 default: 303 gcc_unreachable (); 304 break; 305 } 306 307 /* For all wrapping arithmetic wrap the result. */ 308 if (TYPE_OVERFLOW_WRAPS (type)) 309 res = wrap (res, TYPE_PRECISION (type)); 310 311 return res; 312} 313 314/* Returns a linear expression for tree T evaluated in PBB. */ 315 316static isl_pw_aff * 317create_pw_aff_from_tree (poly_bb_p pbb, loop_p loop, tree t) 318{ 319 scop_p scop = PBB_SCOP (pbb); 320 321 t = cached_scalar_evolution_in_region (scop->scop_info->region, loop, t); 322 323 gcc_assert (!chrec_contains_undetermined (t)); 324 gcc_assert (!automatically_generated_chrec_p (t)); 325 326 return extract_affine (scop, t, isl_set_get_space (pbb->domain)); 327} 328 329/* Add conditional statement STMT to pbb. CODE is used as the comparison 330 operator. This allows us to invert the condition or to handle 331 inequalities. */ 332 333static void 334add_condition_to_pbb (poly_bb_p pbb, gcond *stmt, enum tree_code code) 335{ 336 loop_p loop = gimple_bb (stmt)->loop_father; 337 isl_pw_aff *lhs = create_pw_aff_from_tree (pbb, loop, gimple_cond_lhs (stmt)); 338 isl_pw_aff *rhs = create_pw_aff_from_tree (pbb, loop, gimple_cond_rhs (stmt)); 339 340 isl_set *cond; 341 switch (code) 342 { 343 case LT_EXPR: 344 cond = isl_pw_aff_lt_set (lhs, rhs); 345 break; 346 347 case GT_EXPR: 348 cond = isl_pw_aff_gt_set (lhs, rhs); 349 break; 350 351 case LE_EXPR: 352 cond = isl_pw_aff_le_set (lhs, rhs); 353 break; 354 355 case GE_EXPR: 356 cond = isl_pw_aff_ge_set (lhs, rhs); 357 break; 358 359 case EQ_EXPR: 360 cond = isl_pw_aff_eq_set (lhs, rhs); 361 break; 362 363 case NE_EXPR: 364 cond = isl_pw_aff_ne_set (lhs, rhs); 365 break; 366 367 default: 368 gcc_unreachable (); 369 } 370 371 cond = isl_set_coalesce (cond); 372 cond = isl_set_set_tuple_id (cond, isl_set_get_tuple_id (pbb->domain)); 373 pbb->domain = isl_set_coalesce (isl_set_intersect (pbb->domain, cond)); 374} 375 376/* Add conditions to the domain of PBB. */ 377 378static void 379add_conditions_to_domain (poly_bb_p pbb) 380{ 381 unsigned int i; 382 gimple *stmt; 383 gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); 384 385 if (GBB_CONDITIONS (gbb).is_empty ()) 386 return; 387 388 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt) 389 switch (gimple_code (stmt)) 390 { 391 case GIMPLE_COND: 392 { 393 /* Don't constrain on anything else than INTEGER_TYPE. */ 394 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt))) != INTEGER_TYPE) 395 break; 396 397 gcond *cond_stmt = as_a <gcond *> (stmt); 398 enum tree_code code = gimple_cond_code (cond_stmt); 399 400 /* The conditions for ELSE-branches are inverted. */ 401 if (!GBB_CONDITION_CASES (gbb)[i]) 402 code = invert_tree_comparison (code, false); 403 404 add_condition_to_pbb (pbb, cond_stmt, code); 405 break; 406 } 407 408 default: 409 gcc_unreachable (); 410 break; 411 } 412} 413 414/* Add constraints on the possible values of parameter P from the type 415 of P. */ 416 417static void 418add_param_constraints (scop_p scop, graphite_dim_t p, tree parameter) 419{ 420 tree type = TREE_TYPE (parameter); 421 value_range r; 422 wide_int min, max; 423 424 gcc_assert (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)); 425 426 if (INTEGRAL_TYPE_P (type) 427 && get_range_query (cfun)->range_of_expr (r, parameter) 428 && !r.undefined_p ()) 429 { 430 min = r.lower_bound (); 431 max = r.upper_bound (); 432 } 433 else 434 { 435 min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)); 436 max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); 437 } 438 439 isl_space *space = isl_set_get_space (scop->param_context); 440 isl_constraint *c = isl_inequality_alloc (isl_local_space_from_space (space)); 441 isl_val *v = isl_val_int_from_wi (scop->isl_context, 442 widest_int::from (min, TYPE_SIGN (type))); 443 v = isl_val_neg (v); 444 c = isl_constraint_set_constant_val (c, v); 445 c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, 1); 446 scop->param_context = isl_set_coalesce 447 (isl_set_add_constraint (scop->param_context, c)); 448 449 space = isl_set_get_space (scop->param_context); 450 c = isl_inequality_alloc (isl_local_space_from_space (space)); 451 v = isl_val_int_from_wi (scop->isl_context, 452 widest_int::from (max, TYPE_SIGN (type))); 453 c = isl_constraint_set_constant_val (c, v); 454 c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, -1); 455 scop->param_context = isl_set_coalesce 456 (isl_set_add_constraint (scop->param_context, c)); 457} 458 459/* Add a constrain to the ACCESSES polyhedron for the alias set of 460 data reference DR. ACCESSP_NB_DIMS is the dimension of the 461 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration 462 domain. */ 463 464static isl_map * 465pdr_add_alias_set (isl_map *acc, dr_info &dri) 466{ 467 isl_constraint *c = isl_equality_alloc 468 (isl_local_space_from_space (isl_map_get_space (acc))); 469 /* Positive numbers for all alias sets. */ 470 c = isl_constraint_set_constant_si (c, -dri.alias_set); 471 c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1); 472 473 return isl_map_add_constraint (acc, c); 474} 475 476/* Assign the affine expression INDEX to the output dimension POS of 477 MAP and return the result. */ 478 479static isl_map * 480set_index (isl_map *map, int pos, isl_pw_aff *index) 481{ 482 isl_map *index_map; 483 int len = isl_map_dim (map, isl_dim_out); 484 isl_id *id; 485 486 index_map = isl_map_from_pw_aff (index); 487 index_map = isl_map_insert_dims (index_map, isl_dim_out, 0, pos); 488 index_map = isl_map_add_dims (index_map, isl_dim_out, len - pos - 1); 489 490 id = isl_map_get_tuple_id (map, isl_dim_out); 491 index_map = isl_map_set_tuple_id (index_map, isl_dim_out, id); 492 id = isl_map_get_tuple_id (map, isl_dim_in); 493 index_map = isl_map_set_tuple_id (index_map, isl_dim_in, id); 494 495 return isl_map_intersect (map, index_map); 496} 497 498/* Add to ACCESSES polyhedron equalities defining the access functions 499 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES 500 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain. 501 PBB is the poly_bb_p that contains the data reference DR. */ 502 503static isl_map * 504pdr_add_memory_accesses (isl_map *acc, dr_info &dri) 505{ 506 data_reference_p dr = dri.dr; 507 poly_bb_p pbb = dri.pbb; 508 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr); 509 scop_p scop = PBB_SCOP (pbb); 510 511 for (i = 0; i < nb_subscripts; i++) 512 { 513 isl_pw_aff *aff; 514 tree afn = DR_ACCESS_FN (dr, i); 515 516 aff = extract_affine (scop, afn, 517 isl_space_domain (isl_map_get_space (acc))); 518 acc = set_index (acc, nb_subscripts - i , aff); 519 } 520 521 return isl_map_coalesce (acc); 522} 523 524/* Return true when the LOW and HIGH bounds of an array reference REF are valid 525 to extract constraints on accessed elements of the array. Returning false is 526 the conservative answer. */ 527 528static bool 529bounds_are_valid (tree ref, tree low, tree high) 530{ 531 if (!high) 532 return false; 533 534 if (!tree_fits_shwi_p (low) 535 || !tree_fits_shwi_p (high)) 536 return false; 537 538 /* 1-element arrays at end of structures may extend over 539 their declared size. */ 540 if (array_at_struct_end_p (ref) 541 && operand_equal_p (low, high, 0)) 542 return false; 543 544 /* Fortran has some arrays where high bound is -1 and low is 0. */ 545 if (integer_onep (fold_build2 (LT_EXPR, boolean_type_node, high, low))) 546 return false; 547 548 return true; 549} 550 551/* Add constrains representing the size of the accessed data to the 552 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the 553 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration 554 domain. */ 555 556static isl_set * 557pdr_add_data_dimensions (isl_set *subscript_sizes, scop_p scop, 558 data_reference_p dr) 559{ 560 tree ref = DR_REF (dr); 561 562 int nb_subscripts = DR_NUM_DIMENSIONS (dr); 563 for (int i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0)) 564 { 565 if (TREE_CODE (ref) != ARRAY_REF) 566 return subscript_sizes; 567 568 tree low = array_ref_low_bound (ref); 569 tree high = array_ref_up_bound (ref); 570 571 if (!bounds_are_valid (ref, low, high)) 572 continue; 573 574 isl_space *space = isl_set_get_space (subscript_sizes); 575 isl_pw_aff *lb = extract_affine_int (low, isl_space_copy (space)); 576 isl_pw_aff *ub = extract_affine_int (high, isl_space_copy (space)); 577 578 /* high >= 0 */ 579 isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub)); 580 valid = isl_set_project_out (valid, isl_dim_set, 0, 581 isl_set_dim (valid, isl_dim_set)); 582 scop->param_context = isl_set_coalesce 583 (isl_set_intersect (scop->param_context, valid)); 584 585 isl_aff *aff 586 = isl_aff_zero_on_domain (isl_local_space_from_space (space)); 587 aff = isl_aff_add_coefficient_si (aff, isl_dim_in, i + 1, 1); 588 isl_set *univ 589 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff))); 590 isl_pw_aff *index = isl_pw_aff_alloc (univ, aff); 591 592 isl_id *id = isl_set_get_tuple_id (subscript_sizes); 593 lb = isl_pw_aff_set_tuple_id (lb, isl_dim_in, isl_id_copy (id)); 594 ub = isl_pw_aff_set_tuple_id (ub, isl_dim_in, id); 595 596 /* low <= sub_i <= high */ 597 isl_set *lbs = isl_pw_aff_ge_set (isl_pw_aff_copy (index), lb); 598 isl_set *ubs = isl_pw_aff_le_set (index, ub); 599 subscript_sizes = isl_set_intersect (subscript_sizes, lbs); 600 subscript_sizes = isl_set_intersect (subscript_sizes, ubs); 601 } 602 603 return isl_set_coalesce (subscript_sizes); 604} 605 606/* Build data accesses for DRI. */ 607 608static void 609build_poly_dr (dr_info &dri) 610{ 611 isl_map *acc; 612 isl_set *subscript_sizes; 613 poly_bb_p pbb = dri.pbb; 614 data_reference_p dr = dri.dr; 615 scop_p scop = PBB_SCOP (pbb); 616 isl_id *id = isl_id_for_dr (scop); 617 618 { 619 isl_space *dc = isl_set_get_space (pbb->domain); 620 int nb_out = 1 + DR_NUM_DIMENSIONS (dr); 621 isl_space *space = isl_space_add_dims (isl_space_from_domain (dc), 622 isl_dim_out, nb_out); 623 624 acc = isl_map_universe (space); 625 acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_copy (id)); 626 } 627 628 acc = pdr_add_alias_set (acc, dri); 629 acc = pdr_add_memory_accesses (acc, dri); 630 631 { 632 int nb = 1 + DR_NUM_DIMENSIONS (dr); 633 isl_space *space = isl_space_set_alloc (scop->isl_context, 0, nb); 634 635 space = isl_space_set_tuple_id (space, isl_dim_set, id); 636 subscript_sizes = isl_set_nat_universe (space); 637 subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0, 638 dri.alias_set); 639 subscript_sizes = pdr_add_data_dimensions (subscript_sizes, scop, dr); 640 } 641 642 new_poly_dr (pbb, DR_STMT (dr), DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, 643 acc, subscript_sizes); 644} 645 646static void 647build_poly_sr_1 (poly_bb_p pbb, gimple *stmt, tree var, enum poly_dr_type kind, 648 isl_map *acc, isl_set *subscript_sizes) 649{ 650 scop_p scop = PBB_SCOP (pbb); 651 /* Each scalar variables has a unique alias set number starting from 652 the maximum alias set assigned to a dr. */ 653 int alias_set = scop->max_alias_set + SSA_NAME_VERSION (var); 654 subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0, 655 alias_set); 656 657 /* Add a constrain to the ACCESSES polyhedron for the alias set of 658 data reference DR. */ 659 isl_constraint *c 660 = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (acc))); 661 c = isl_constraint_set_constant_si (c, -alias_set); 662 c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1); 663 664 new_poly_dr (pbb, stmt, kind, isl_map_add_constraint (acc, c), 665 subscript_sizes); 666} 667 668/* Record all cross basic block scalar variables in PBB. */ 669 670static void 671build_poly_sr (poly_bb_p pbb) 672{ 673 scop_p scop = PBB_SCOP (pbb); 674 gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); 675 vec<scalar_use> &reads = gbb->read_scalar_refs; 676 vec<tree> &writes = gbb->write_scalar_refs; 677 678 isl_space *dc = isl_set_get_space (pbb->domain); 679 int nb_out = 1; 680 isl_space *space = isl_space_add_dims (isl_space_from_domain (dc), 681 isl_dim_out, nb_out); 682 isl_id *id = isl_id_for_dr (scop); 683 space = isl_space_set_tuple_id (space, isl_dim_set, isl_id_copy (id)); 684 isl_map *acc = isl_map_universe (isl_space_copy (space)); 685 acc = isl_map_set_tuple_id (acc, isl_dim_out, id); 686 isl_set *subscript_sizes = isl_set_nat_universe (space); 687 688 int i; 689 tree var; 690 FOR_EACH_VEC_ELT (writes, i, var) 691 build_poly_sr_1 (pbb, SSA_NAME_DEF_STMT (var), var, PDR_WRITE, 692 isl_map_copy (acc), isl_set_copy (subscript_sizes)); 693 694 scalar_use *use; 695 FOR_EACH_VEC_ELT (reads, i, use) 696 build_poly_sr_1 (pbb, use->first, use->second, PDR_READ, isl_map_copy (acc), 697 isl_set_copy (subscript_sizes)); 698 699 isl_map_free (acc); 700 isl_set_free (subscript_sizes); 701} 702 703/* Build data references in SCOP. */ 704 705static void 706build_scop_drs (scop_p scop) 707{ 708 int i; 709 dr_info *dri; 710 FOR_EACH_VEC_ELT (scop->drs, i, dri) 711 build_poly_dr (*dri); 712 713 poly_bb_p pbb; 714 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) 715 build_poly_sr (pbb); 716} 717 718/* Add to the iteration DOMAIN one extra dimension for LOOP->num. */ 719 720static isl_set * 721add_iter_domain_dimension (__isl_take isl_set *domain, loop_p loop, scop_p scop) 722{ 723 int loop_index = isl_set_dim (domain, isl_dim_set); 724 domain = isl_set_add_dims (domain, isl_dim_set, 1); 725 char name[50]; 726 snprintf (name, sizeof(name), "i%d", loop->num); 727 isl_id *label = isl_id_alloc (scop->isl_context, name, NULL); 728 return isl_set_set_dim_id (domain, isl_dim_set, loop_index, label); 729} 730 731/* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */ 732 733static isl_set * 734add_loop_constraints (scop_p scop, __isl_take isl_set *domain, loop_p loop, 735 loop_p context) 736{ 737 if (loop == context) 738 return domain; 739 const sese_l ®ion = scop->scop_info->region; 740 if (!loop_in_sese_p (loop, region)) 741 return domain; 742 743 /* Recursion all the way up to the context loop. */ 744 domain = add_loop_constraints (scop, domain, loop_outer (loop), context); 745 746 /* Then, build constraints over the loop in post-order: outer to inner. */ 747 748 int loop_index = isl_set_dim (domain, isl_dim_set); 749 if (dump_file) 750 fprintf (dump_file, "[sese-to-poly] adding one extra dimension to the " 751 "domain for loop_%d.\n", loop->num); 752 domain = add_iter_domain_dimension (domain, loop, scop); 753 isl_space *space = isl_set_get_space (domain); 754 755 /* 0 <= loop_i */ 756 isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space)); 757 isl_constraint *c = isl_inequality_alloc (ls); 758 c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, 1); 759 if (dump_file) 760 { 761 fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: "); 762 print_isl_constraint (dump_file, c); 763 } 764 domain = isl_set_add_constraint (domain, c); 765 766 tree nb_iters = number_of_latch_executions (loop); 767 if (TREE_CODE (nb_iters) == INTEGER_CST) 768 { 769 /* loop_i <= cst_nb_iters */ 770 isl_local_space *ls = isl_local_space_from_space (space); 771 isl_constraint *c = isl_inequality_alloc (ls); 772 c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1); 773 isl_val *v 774 = isl_val_int_from_wi (scop->isl_context, wi::to_widest (nb_iters)); 775 c = isl_constraint_set_constant_val (c, v); 776 return isl_set_add_constraint (domain, c); 777 } 778 /* loop_i <= expr_nb_iters */ 779 gcc_assert (!chrec_contains_undetermined (nb_iters)); 780 nb_iters = cached_scalar_evolution_in_region (region, loop, nb_iters); 781 gcc_assert (!chrec_contains_undetermined (nb_iters)); 782 783 isl_pw_aff *aff_nb_iters = extract_affine (scop, nb_iters, 784 isl_space_copy (space)); 785 isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters)); 786 valid = isl_set_project_out (valid, isl_dim_set, 0, 787 isl_set_dim (valid, isl_dim_set)); 788 789 if (valid) 790 scop->param_context = isl_set_intersect (scop->param_context, valid); 791 792 ls = isl_local_space_from_space (isl_space_copy (space)); 793 isl_aff *loop_i = isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls), 794 isl_dim_in, loop_index, 1); 795 isl_set *le = isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i), 796 isl_pw_aff_copy (aff_nb_iters)); 797 if (dump_file) 798 { 799 fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: "); 800 print_isl_set (dump_file, le); 801 } 802 domain = isl_set_intersect (domain, le); 803 804 widest_int nit; 805 if (!max_stmt_executions (loop, &nit)) 806 { 807 isl_pw_aff_free (aff_nb_iters); 808 isl_space_free (space); 809 return domain; 810 } 811 812 /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we 813 do not know whether the loop executes at least once. */ 814 --nit; 815 816 isl_pw_aff *approx = extract_affine_wi (nit, isl_space_copy (space)); 817 isl_set *x = isl_pw_aff_ge_set (approx, aff_nb_iters); 818 x = isl_set_project_out (x, isl_dim_set, 0, 819 isl_set_dim (x, isl_dim_set)); 820 scop->param_context = isl_set_intersect (scop->param_context, x); 821 822 ls = isl_local_space_from_space (space); 823 c = isl_inequality_alloc (ls); 824 c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1); 825 isl_val *v = isl_val_int_from_wi (scop->isl_context, nit); 826 c = isl_constraint_set_constant_val (c, v); 827 828 if (dump_file) 829 { 830 fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: "); 831 print_isl_constraint (dump_file, c); 832 } 833 834 return isl_set_add_constraint (domain, c); 835} 836 837/* Builds the original iteration domains for each pbb in the SCOP. */ 838 839static int 840build_iteration_domains (scop_p scop, __isl_keep isl_set *context, 841 int index, loop_p context_loop) 842{ 843 loop_p current = pbb_loop (scop->pbbs[index]); 844 isl_set *domain = isl_set_copy (context); 845 domain = add_loop_constraints (scop, domain, current, context_loop); 846 const sese_l ®ion = scop->scop_info->region; 847 848 int i; 849 poly_bb_p pbb; 850 FOR_EACH_VEC_ELT_FROM (scop->pbbs, i, pbb, index) 851 { 852 loop_p loop = pbb_loop (pbb); 853 if (current == loop) 854 { 855 pbb->iterators = isl_set_copy (domain); 856 pbb->domain = isl_set_copy (domain); 857 pbb->domain = isl_set_set_tuple_id (pbb->domain, 858 isl_id_for_pbb (scop, pbb)); 859 add_conditions_to_domain (pbb); 860 861 if (dump_file) 862 { 863 fprintf (dump_file, "[sese-to-poly] set pbb_%d->domain: ", 864 pbb_index (pbb)); 865 print_isl_set (dump_file, domain); 866 } 867 continue; 868 } 869 870 while (loop_in_sese_p (loop, region) 871 && current != loop) 872 loop = loop_outer (loop); 873 874 if (current != loop) 875 { 876 /* A statement in a different loop nest than CURRENT loop. */ 877 isl_set_free (domain); 878 return i; 879 } 880 881 /* A statement nested in the CURRENT loop. */ 882 i = build_iteration_domains (scop, domain, i, current); 883 i--; 884 } 885 886 isl_set_free (domain); 887 return i; 888} 889 890/* Assign dimension for each parameter in SCOP and add constraints for the 891 parameters. */ 892 893static void 894build_scop_context (scop_p scop) 895{ 896 sese_info_p region = scop->scop_info; 897 unsigned nbp = sese_nb_params (region); 898 isl_space *space = isl_space_set_alloc (scop->isl_context, nbp, 0); 899 900 unsigned i; 901 tree e; 902 FOR_EACH_VEC_ELT (region->params, i, e) 903 space = isl_space_set_dim_id (space, isl_dim_param, i, 904 isl_id_for_ssa_name (scop, e)); 905 906 scop->param_context = isl_set_universe (space); 907 908 FOR_EACH_VEC_ELT (region->params, i, e) 909 add_param_constraints (scop, i, e); 910} 911 912/* Return true when loop A is nested in loop B. */ 913 914static bool 915nested_in (loop_p a, loop_p b) 916{ 917 return b == find_common_loop (a, b); 918} 919 920/* Return the loop at a specific SCOP->pbbs[*INDEX]. */ 921static loop_p 922loop_at (scop_p scop, int *index) 923{ 924 return pbb_loop (scop->pbbs[*index]); 925} 926 927/* Return the index of any pbb belonging to loop or a subloop of A. */ 928 929static int 930index_outermost_in_loop (loop_p a, scop_p scop) 931{ 932 int i, outermost = -1; 933 int last_depth = -1; 934 poly_bb_p pbb; 935 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) 936 if (nested_in (pbb_loop (pbb), a) 937 && (last_depth == -1 938 || last_depth > (int) loop_depth (pbb_loop (pbb)))) 939 { 940 outermost = i; 941 last_depth = loop_depth (pbb_loop (pbb)); 942 } 943 return outermost; 944} 945 946/* Return the index of any pbb belonging to loop or a subloop of A. */ 947 948static int 949index_pbb_in_loop (loop_p a, scop_p scop) 950{ 951 int i; 952 poly_bb_p pbb; 953 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) 954 if (pbb_loop (pbb) == a) 955 return i; 956 return -1; 957} 958 959static poly_bb_p 960outermost_pbb_in (loop_p loop, scop_p scop) 961{ 962 int x = index_pbb_in_loop (loop, scop); 963 if (x == -1) 964 x = index_outermost_in_loop (loop, scop); 965 return scop->pbbs[x]; 966} 967 968static isl_schedule * 969add_in_sequence (__isl_take isl_schedule *a, __isl_take isl_schedule *b) 970{ 971 gcc_assert (a || b); 972 973 if (!a) 974 return b; 975 976 if (!b) 977 return a; 978 979 return isl_schedule_sequence (a, b); 980} 981 982struct map_to_dimension_data { 983 int n; 984 isl_union_pw_multi_aff *res; 985}; 986 987/* Create a function that maps the elements of SET to its N-th dimension and add 988 it to USER->res. */ 989 990static isl_stat 991add_outer_projection (__isl_take isl_set *set, void *user) 992{ 993 struct map_to_dimension_data *data = (struct map_to_dimension_data *) user; 994 int dim = isl_set_dim (set, isl_dim_set); 995 isl_space *space = isl_set_get_space (set); 996 997 gcc_assert (dim >= data->n); 998 isl_pw_multi_aff *pma 999 = isl_pw_multi_aff_project_out_map (space, isl_dim_set, data->n, 1000 dim - data->n); 1001 data->res = isl_union_pw_multi_aff_add_pw_multi_aff (data->res, pma); 1002 1003 isl_set_free (set); 1004 return isl_stat_ok; 1005} 1006 1007/* Return SET in which all inner dimensions above N are removed. */ 1008 1009static isl_multi_union_pw_aff * 1010outer_projection_mupa (__isl_take isl_union_set *set, int n) 1011{ 1012 gcc_assert (n >= 0); 1013 gcc_assert (set); 1014 gcc_assert (!isl_union_set_is_empty (set)); 1015 1016 isl_space *space = isl_union_set_get_space (set); 1017 isl_union_pw_multi_aff *pwaff = isl_union_pw_multi_aff_empty (space); 1018 1019 struct map_to_dimension_data data = {n, pwaff}; 1020 1021 if (isl_union_set_foreach_set (set, &add_outer_projection, &data) < 0) 1022 data.res = isl_union_pw_multi_aff_free (data.res); 1023 1024 isl_union_set_free (set); 1025 return isl_multi_union_pw_aff_from_union_pw_multi_aff (data.res); 1026} 1027 1028/* Embed SCHEDULE in the constraints of the LOOP domain. */ 1029 1030static isl_schedule * 1031add_loop_schedule (__isl_take isl_schedule *schedule, loop_p loop, 1032 scop_p scop) 1033{ 1034 poly_bb_p pbb = outermost_pbb_in (loop, scop); 1035 isl_set *iterators = pbb->iterators; 1036 1037 int empty = isl_set_is_empty (iterators); 1038 if (empty < 0 || empty) 1039 return empty < 0 ? isl_schedule_free (schedule) : schedule; 1040 1041 isl_union_set *domain = isl_schedule_get_domain (schedule); 1042 /* We cannot apply an empty domain to pbbs in this loop so return early. */ 1043 if (isl_union_set_is_empty (domain)) 1044 { 1045 isl_union_set_free (domain); 1046 return schedule; 1047 } 1048 1049 isl_space *space = isl_set_get_space (iterators); 1050 int loop_index = isl_space_dim (space, isl_dim_set) - 1; 1051 1052 loop_p ploop = pbb_loop (pbb); 1053 while (loop != ploop) 1054 { 1055 --loop_index; 1056 ploop = loop_outer (ploop); 1057 } 1058 1059 isl_local_space *ls = isl_local_space_from_space (space); 1060 isl_aff *aff = isl_aff_var_on_domain (ls, isl_dim_set, loop_index); 1061 isl_multi_aff *prefix = isl_multi_aff_from_aff (aff); 1062 char name[50]; 1063 snprintf (name, sizeof(name), "L_%d", loop->num); 1064 isl_id *label = isl_id_alloc (isl_schedule_get_ctx (schedule), 1065 name, NULL); 1066 prefix = isl_multi_aff_set_tuple_id (prefix, isl_dim_out, label); 1067 1068 int n = isl_multi_aff_dim (prefix, isl_dim_in); 1069 isl_multi_union_pw_aff *mupa = outer_projection_mupa (domain, n); 1070 mupa = isl_multi_union_pw_aff_apply_multi_aff (mupa, prefix); 1071 return isl_schedule_insert_partial_schedule (schedule, mupa); 1072} 1073 1074/* Build schedule for the pbb at INDEX. */ 1075 1076static isl_schedule * 1077build_schedule_pbb (scop_p scop, int *index) 1078{ 1079 poly_bb_p pbb = scop->pbbs[*index]; 1080 ++*index; 1081 isl_set *domain = isl_set_copy (pbb->domain); 1082 isl_union_set *ud = isl_union_set_from_set (domain); 1083 return isl_schedule_from_domain (ud); 1084} 1085 1086static isl_schedule *build_schedule_loop_nest (scop_p, int *, loop_p); 1087 1088/* Build the schedule of the loop containing the SCOP pbb at INDEX. */ 1089 1090static isl_schedule * 1091build_schedule_loop (scop_p scop, int *index) 1092{ 1093 int max = scop->pbbs.length (); 1094 gcc_assert (*index < max); 1095 loop_p loop = loop_at (scop, index); 1096 1097 isl_schedule *s = NULL; 1098 while (nested_in (loop_at (scop, index), loop)) 1099 { 1100 if (loop == loop_at (scop, index)) 1101 s = add_in_sequence (s, build_schedule_pbb (scop, index)); 1102 else 1103 s = add_in_sequence (s, build_schedule_loop_nest (scop, index, loop)); 1104 1105 if (*index == max) 1106 break; 1107 } 1108 1109 return add_loop_schedule (s, loop, scop); 1110} 1111 1112/* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops. 1113 When CONTEXT_LOOP is null, embed the schedule in all loops contained in the 1114 SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the 1115 maximal loop nest contained within CONTEXT_LOOP. */ 1116 1117static isl_schedule * 1118embed_in_surrounding_loops (__isl_take isl_schedule *s, scop_p scop, 1119 loop_p loop, int *index, loop_p context_loop) 1120{ 1121 loop_p outer = loop_outer (loop); 1122 sese_l region = scop->scop_info->region; 1123 if (context_loop == outer 1124 || !loop_in_sese_p (outer, region)) 1125 return s; 1126 1127 int max = scop->pbbs.length (); 1128 if (*index == max 1129 || (context_loop && !nested_in (loop_at (scop, index), context_loop)) 1130 || (!context_loop 1131 && !loop_in_sese_p (find_common_loop (outer, loop_at (scop, index)), 1132 region))) 1133 return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop), 1134 scop, outer, index, context_loop); 1135 1136 bool a_pbb; 1137 while ((a_pbb = (outer == loop_at (scop, index))) 1138 || nested_in (loop_at (scop, index), outer)) 1139 { 1140 if (a_pbb) 1141 s = add_in_sequence (s, build_schedule_pbb (scop, index)); 1142 else 1143 s = add_in_sequence (s, build_schedule_loop (scop, index)); 1144 1145 if (*index == max) 1146 break; 1147 } 1148 1149 /* We reached the end of the OUTER loop: embed S in OUTER. */ 1150 return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop), scop, 1151 outer, index, context_loop); 1152} 1153 1154/* Build schedule for the full loop nest containing the pbb at INDEX. When 1155 CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP 1156 surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop 1157 nest contained within CONTEXT_LOOP. */ 1158 1159static isl_schedule * 1160build_schedule_loop_nest (scop_p scop, int *index, loop_p context_loop) 1161{ 1162 gcc_assert (*index != (int) scop->pbbs.length ()); 1163 1164 loop_p loop = loop_at (scop, index); 1165 isl_schedule *s = build_schedule_loop (scop, index); 1166 return embed_in_surrounding_loops (s, scop, loop, index, context_loop); 1167} 1168 1169/* Build the schedule of the SCOP. */ 1170 1171static void 1172build_original_schedule (scop_p scop) 1173{ 1174 int i = 0; 1175 int n = scop->pbbs.length (); 1176 while (i < n) 1177 { 1178 poly_bb_p pbb = scop->pbbs[i]; 1179 isl_schedule *s = NULL; 1180 if (!loop_in_sese_p (pbb_loop (pbb), scop->scop_info->region)) 1181 s = build_schedule_pbb (scop, &i); 1182 else 1183 s = build_schedule_loop_nest (scop, &i, NULL); 1184 1185 scop->original_schedule = add_in_sequence (scop->original_schedule, s); 1186 } 1187 1188 if (dump_file) 1189 { 1190 fprintf (dump_file, "[sese-to-poly] original schedule:\n"); 1191 print_isl_schedule (dump_file, scop->original_schedule); 1192 } 1193} 1194 1195/* Builds the polyhedral representation for a SESE region. */ 1196 1197bool 1198build_poly_scop (scop_p scop) 1199{ 1200 int old_err = isl_options_get_on_error (scop->isl_context); 1201 isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE); 1202 1203 build_scop_context (scop); 1204 1205 unsigned i = 0; 1206 unsigned n = scop->pbbs.length (); 1207 while (i < n) 1208 i = build_iteration_domains (scop, scop->param_context, i, NULL); 1209 1210 build_scop_drs (scop); 1211 build_original_schedule (scop); 1212 1213 enum isl_error err = isl_ctx_last_error (scop->isl_context); 1214 isl_ctx_reset_error (scop->isl_context); 1215 isl_options_set_on_error (scop->isl_context, old_err); 1216 if (err != isl_error_none 1217 && dump_enabled_p ()) 1218 dump_printf (MSG_MISSED_OPTIMIZATION, 1219 "ISL error while building poly scop\n"); 1220 1221 return err == isl_error_none; 1222} 1223#endif /* HAVE_isl */ 1224