1 /* Interchange heuristics and transform for loop interchange on 2 polyhedral representation. 3 4 Copyright (C) 2009, 2010 Free Software Foundation, Inc. 5 Contributed by Sebastian Pop <sebastian.pop@amd.com> and 6 Harsha Jagasia <harsha.jagasia@amd.com>. 7 8 This file is part of GCC. 9 10 GCC is free software; you can redistribute it and/or modify 11 it under the terms of the GNU General Public License as published by 12 the Free Software Foundation; either version 3, or (at your option) 13 any later version. 14 15 GCC is distributed in the hope that it will be useful, 16 but WITHOUT ANY WARRANTY; without even the implied warranty of 17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 GNU General Public License for more details. 19 20 You should have received a copy of the GNU General Public License 21 along with GCC; see the file COPYING3. If not see 22 <http://www.gnu.org/licenses/>. */ 23 #include "config.h" 24 #include "system.h" 25 #include "coretypes.h" 26 #include "tree-flow.h" 27 #include "tree-dump.h" 28 #include "cfgloop.h" 29 #include "tree-chrec.h" 30 #include "tree-data-ref.h" 31 #include "tree-scalar-evolution.h" 32 #include "sese.h" 33 34 #ifdef HAVE_cloog 35 #include "ppl_c.h" 36 #include "graphite-ppl.h" 37 #include "graphite-poly.h" 38 39 /* Builds a linear expression, of dimension DIM, representing PDR's 40 memory access: 41 42 L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}. 43 44 For an array A[10][20] with two subscript locations s0 and s1, the 45 linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0 46 corresponds to a memory stride of 20. 47 48 OFFSET is a number of dimensions to prepend before the 49 subscript dimensions: s_0, s_1, ..., s_n. 50 51 Thus, the final linear expression has the following format: 52 0 .. 0_{offset} | 0 .. 0_{nit} | 0 .. 0_{gd} | 0 | c_0 c_1 ... c_n 53 where the expression itself is: 54 c_0 * s_0 + c_1 * s_1 + ... c_n * s_n. */ 55 56 static ppl_Linear_Expression_t 57 build_linearized_memory_access (ppl_dimension_type offset, poly_dr_p pdr) 58 { 59 ppl_Linear_Expression_t res; 60 ppl_Linear_Expression_t le; 61 ppl_dimension_type i; 62 ppl_dimension_type first = pdr_subscript_dim (pdr, 0); 63 ppl_dimension_type last = pdr_subscript_dim (pdr, PDR_NB_SUBSCRIPTS (pdr)); 64 mpz_t size, sub_size; 65 graphite_dim_t dim = offset + pdr_dim (pdr); 66 67 ppl_new_Linear_Expression_with_dimension (&res, dim); 68 69 mpz_init (size); 70 mpz_set_si (size, 1); 71 mpz_init (sub_size); 72 mpz_set_si (sub_size, 1); 73 74 for (i = last - 1; i >= first; i--) 75 { 76 ppl_set_coef_gmp (res, i + offset, size); 77 78 ppl_new_Linear_Expression_with_dimension (&le, dim - offset); 79 ppl_set_coef (le, i, 1); 80 ppl_max_for_le_pointset (PDR_ACCESSES (pdr), le, sub_size); 81 mpz_mul (size, size, sub_size); 82 ppl_delete_Linear_Expression (le); 83 } 84 85 mpz_clear (sub_size); 86 mpz_clear (size); 87 return res; 88 } 89 90 /* Builds a partial difference equations and inserts them 91 into pointset powerset polyhedron P. Polyhedron is assumed 92 to have the format: T|I|T'|I'|G|S|S'|l1|l2. 93 94 TIME_DEPTH is the time dimension w.r.t. which we are 95 differentiating. 96 OFFSET represents the number of dimensions between 97 columns t_{time_depth} and t'_{time_depth}. 98 DIM_SCTR is the number of scattering dimensions. It is 99 essentially the dimensionality of the T vector. 100 101 The following equations are inserted into the polyhedron P: 102 | t_1 = t_1' 103 | ... 104 | t_{time_depth-1} = t'_{time_depth-1} 105 | t_{time_depth} = t'_{time_depth} + 1 106 | t_{time_depth+1} = t'_{time_depth + 1} 107 | ... 108 | t_{dim_sctr} = t'_{dim_sctr}. */ 109 110 static void 111 build_partial_difference (ppl_Pointset_Powerset_C_Polyhedron_t *p, 112 ppl_dimension_type time_depth, 113 ppl_dimension_type offset, 114 ppl_dimension_type dim_sctr) 115 { 116 ppl_Constraint_t new_cstr; 117 ppl_Linear_Expression_t le; 118 ppl_dimension_type i; 119 ppl_dimension_type dim; 120 ppl_Pointset_Powerset_C_Polyhedron_t temp; 121 122 /* Add the equality: t_{time_depth} = t'_{time_depth} + 1. 123 This is the core part of this alogrithm, since this 124 constraint asks for the memory access stride (difference) 125 between two consecutive points in time dimensions. */ 126 127 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (*p, &dim); 128 ppl_new_Linear_Expression_with_dimension (&le, dim); 129 ppl_set_coef (le, time_depth, 1); 130 ppl_set_coef (le, time_depth + offset, -1); 131 ppl_set_inhomogeneous (le, 1); 132 ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL); 133 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (*p, new_cstr); 134 ppl_delete_Linear_Expression (le); 135 ppl_delete_Constraint (new_cstr); 136 137 /* Add equalities: 138 | t1 = t1' 139 | ... 140 | t_{time_depth-1} = t'_{time_depth-1} 141 | t_{time_depth+1} = t'_{time_depth+1} 142 | ... 143 | t_{dim_sctr} = t'_{dim_sctr} 144 145 This means that all the time dimensions are equal except for 146 time_depth, where the constraint is t_{depth} = t'_{depth} + 1 147 step. More to this: we should be carefull not to add equalities 148 to the 'coupled' dimensions, which happens when the one dimension 149 is stripmined dimension, and the other dimension corresponds 150 to the point loop inside stripmined dimension. */ 151 152 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&temp, *p); 153 154 for (i = 0; i < dim_sctr; i++) 155 if (i != time_depth) 156 { 157 ppl_new_Linear_Expression_with_dimension (&le, dim); 158 ppl_set_coef (le, i, 1); 159 ppl_set_coef (le, i + offset, -1); 160 ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL); 161 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (temp, new_cstr); 162 163 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (temp)) 164 { 165 ppl_delete_Pointset_Powerset_C_Polyhedron (temp); 166 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&temp, *p); 167 } 168 else 169 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (*p, new_cstr); 170 ppl_delete_Linear_Expression (le); 171 ppl_delete_Constraint (new_cstr); 172 } 173 174 ppl_delete_Pointset_Powerset_C_Polyhedron (temp); 175 } 176 177 178 /* Set STRIDE to the stride of PDR in memory by advancing by one in 179 the loop at DEPTH. */ 180 181 static void 182 pdr_stride_in_loop (mpz_t stride, graphite_dim_t depth, poly_dr_p pdr) 183 { 184 ppl_dimension_type time_depth; 185 ppl_Linear_Expression_t le, lma; 186 ppl_Constraint_t new_cstr; 187 ppl_dimension_type i, *map; 188 ppl_Pointset_Powerset_C_Polyhedron_t p1, p2, sctr; 189 graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr) + 1; 190 poly_bb_p pbb = PDR_PBB (pdr); 191 ppl_dimension_type offset = pbb_nb_scattering_transform (pbb) 192 + pbb_nb_local_vars (pbb) 193 + pbb_dim_iter_domain (pbb); 194 ppl_dimension_type offsetg = offset + pbb_nb_params (pbb); 195 ppl_dimension_type dim_sctr = pbb_nb_scattering_transform (pbb) 196 + pbb_nb_local_vars (pbb); 197 ppl_dimension_type dim_L1 = offset + offsetg + 2 * nb_subscripts; 198 ppl_dimension_type dim_L2 = offset + offsetg + 2 * nb_subscripts + 1; 199 ppl_dimension_type new_dim = offset + offsetg + 2 * nb_subscripts + 2; 200 201 /* The resulting polyhedron should have the following format: 202 T|I|T'|I'|G|S|S'|l1|l2 203 where: 204 | T = t_1..t_{dim_sctr} 205 | I = i_1..i_{dim_iter_domain} 206 | T'= t'_1..t'_{dim_sctr} 207 | I'= i'_1..i'_{dim_iter_domain} 208 | G = g_1..g_{nb_params} 209 | S = s_1..s_{nb_subscripts} 210 | S'= s'_1..s'_{nb_subscripts} 211 | l1 and l2 are scalars. 212 213 Some invariants: 214 offset = dim_sctr + dim_iter_domain + nb_local_vars 215 offsetg = dim_sctr + dim_iter_domain + nb_local_vars + nb_params. */ 216 217 /* Construct the T|I|0|0|G|0|0|0|0 part. */ 218 { 219 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron 220 (&sctr, PBB_TRANSFORMED_SCATTERING (pbb)); 221 ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed 222 (sctr, 2 * nb_subscripts + 2); 223 ppl_insert_dimensions_pointset (sctr, offset, offset); 224 } 225 226 /* Construct the 0|I|0|0|G|S|0|0|0 part. */ 227 { 228 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron 229 (&p1, PDR_ACCESSES (pdr)); 230 ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed 231 (p1, nb_subscripts + 2); 232 ppl_insert_dimensions_pointset (p1, 0, dim_sctr); 233 ppl_insert_dimensions_pointset (p1, offset, offset); 234 } 235 236 /* Construct the 0|0|0|0|0|S|0|l1|0 part. */ 237 { 238 lma = build_linearized_memory_access (offset + dim_sctr, pdr); 239 ppl_set_coef (lma, dim_L1, -1); 240 ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL); 241 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr); 242 ppl_delete_Linear_Expression (lma); 243 ppl_delete_Constraint (new_cstr); 244 } 245 246 /* Now intersect all the parts to get the polyhedron P1: 247 T|I|0|0|G|0|0|0 |0 248 0|I|0|0|G|S|0|0 |0 249 0|0|0|0|0|S|0|l1|0 250 ------------------ 251 T|I|0|0|G|S|0|l1|0. */ 252 253 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, sctr); 254 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr); 255 256 /* Build P2, which would have the following form: 257 0|0|T'|I'|G|0|S'|0|l2 258 259 P2 is built, by remapping the P1 polyhedron: 260 T|I|0|0|G|S|0|l1|0 261 262 using the following mapping: 263 T->T' 264 I->I' 265 S->S' 266 l1->l2. */ 267 { 268 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron 269 (&p2, p1); 270 271 map = ppl_new_id_map (new_dim); 272 273 /* TI -> T'I'. */ 274 for (i = 0; i < offset; i++) 275 ppl_interchange (map, i, i + offset); 276 277 /* l1 -> l2. */ 278 ppl_interchange (map, dim_L1, dim_L2); 279 280 /* S -> S'. */ 281 for (i = 0; i < nb_subscripts; i++) 282 ppl_interchange (map, offset + offsetg + i, 283 offset + offsetg + nb_subscripts + i); 284 285 ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim); 286 free (map); 287 } 288 289 time_depth = psct_dynamic_dim (pbb, depth); 290 291 /* P1 = P1 inter P2. */ 292 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2); 293 build_partial_difference (&p1, time_depth, offset, dim_sctr); 294 295 /* Maximise the expression L2 - L1. */ 296 { 297 ppl_new_Linear_Expression_with_dimension (&le, new_dim); 298 ppl_set_coef (le, dim_L2, 1); 299 ppl_set_coef (le, dim_L1, -1); 300 ppl_max_for_le_pointset (p1, le, stride); 301 } 302 303 if (dump_file && (dump_flags & TDF_DETAILS)) 304 { 305 char *str; 306 void (*gmp_free) (void *, size_t); 307 308 fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d:", 309 pbb_index (pbb), PDR_ID (pdr), (int) depth); 310 str = mpz_get_str (0, 10, stride); 311 fprintf (dump_file, " %s ", str); 312 mp_get_memory_functions (NULL, NULL, &gmp_free); 313 (*gmp_free) (str, strlen (str) + 1); 314 } 315 316 ppl_delete_Pointset_Powerset_C_Polyhedron (p1); 317 ppl_delete_Pointset_Powerset_C_Polyhedron (p2); 318 ppl_delete_Linear_Expression (le); 319 } 320 321 322 /* Sets STRIDES to the sum of all the strides of the data references 323 accessed in LOOP at DEPTH. */ 324 325 static void 326 memory_strides_in_loop_1 (lst_p loop, graphite_dim_t depth, mpz_t strides) 327 { 328 int i, j; 329 lst_p l; 330 poly_dr_p pdr; 331 mpz_t s, n; 332 333 mpz_init (s); 334 mpz_init (n); 335 336 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), j, l) 337 if (LST_LOOP_P (l)) 338 memory_strides_in_loop_1 (l, depth, strides); 339 else 340 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (LST_PBB (l)), i, pdr) 341 { 342 pdr_stride_in_loop (s, depth, pdr); 343 mpz_set_si (n, PDR_NB_REFS (pdr)); 344 mpz_mul (s, s, n); 345 mpz_add (strides, strides, s); 346 } 347 348 mpz_clear (s); 349 mpz_clear (n); 350 } 351 352 /* Sets STRIDES to the sum of all the strides of the data references 353 accessed in LOOP at DEPTH. */ 354 355 static void 356 memory_strides_in_loop (lst_p loop, graphite_dim_t depth, mpz_t strides) 357 { 358 if (mpz_cmp_si (loop->memory_strides, -1) == 0) 359 { 360 mpz_set_si (strides, 0); 361 memory_strides_in_loop_1 (loop, depth, strides); 362 } 363 else 364 mpz_set (strides, loop->memory_strides); 365 } 366 367 /* Return true when the interchange of loops LOOP1 and LOOP2 is 368 profitable. 369 370 Example: 371 372 | int a[100][100]; 373 | 374 | int 375 | foo (int N) 376 | { 377 | int j; 378 | int i; 379 | 380 | for (i = 0; i < N; i++) 381 | for (j = 0; j < N; j++) 382 | a[j][2 * i] += 1; 383 | 384 | return a[N][12]; 385 | } 386 387 The data access A[j][i] is described like this: 388 389 | i j N a s0 s1 1 390 | 0 0 0 1 0 0 -5 = 0 391 | 0 -1 0 0 1 0 0 = 0 392 |-2 0 0 0 0 1 0 = 0 393 | 0 0 0 0 1 0 0 >= 0 394 | 0 0 0 0 0 1 0 >= 0 395 | 0 0 0 0 -1 0 100 >= 0 396 | 0 0 0 0 0 -1 100 >= 0 397 398 The linearized memory access L to A[100][100] is: 399 400 | i j N a s0 s1 1 401 | 0 0 0 0 100 1 0 402 403 TODO: the shown format is not valid as it does not show the fact 404 that the iteration domain "i j" is transformed using the scattering. 405 406 Next, to measure the impact of iterating once in loop "i", we build 407 a maximization problem: first, we add to DR accesses the dimensions 408 k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: this is the polyhedron P1. 409 L1 and L2 are the linearized memory access functions. 410 411 | i j N a s0 s1 k s2 s3 L1 L2 D1 1 412 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5 413 | 0 -1 0 0 1 0 0 0 0 0 0 0 0 = 0 s0 = j 414 |-2 0 0 0 0 1 0 0 0 0 0 0 0 = 0 s1 = 2 * i 415 | 0 0 0 0 1 0 0 0 0 0 0 0 0 >= 0 416 | 0 0 0 0 0 1 0 0 0 0 0 0 0 >= 0 417 | 0 0 0 0 -1 0 0 0 0 0 0 0 100 >= 0 418 | 0 0 0 0 0 -1 0 0 0 0 0 0 100 >= 0 419 | 0 0 0 0 100 1 0 0 0 -1 0 0 0 = 0 L1 = 100 * s0 + s1 420 421 Then, we generate the polyhedron P2 by interchanging the dimensions 422 (s0, s2), (s1, s3), (L1, L2), (k, i) 423 424 | i j N a s0 s1 k s2 s3 L1 L2 D1 1 425 | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5 426 | 0 -1 0 0 0 0 0 1 0 0 0 0 0 = 0 s2 = j 427 | 0 0 0 0 0 0 -2 0 1 0 0 0 0 = 0 s3 = 2 * k 428 | 0 0 0 0 0 0 0 1 0 0 0 0 0 >= 0 429 | 0 0 0 0 0 0 0 0 1 0 0 0 0 >= 0 430 | 0 0 0 0 0 0 0 -1 0 0 0 0 100 >= 0 431 | 0 0 0 0 0 0 0 0 -1 0 0 0 100 >= 0 432 | 0 0 0 0 0 0 0 100 1 0 -1 0 0 = 0 L2 = 100 * s2 + s3 433 434 then we add to P2 the equality k = i + 1: 435 436 |-1 0 0 0 0 0 1 0 0 0 0 0 -1 = 0 k = i + 1 437 438 and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)". 439 440 Similarly, to determine the impact of one iteration on loop "j", we 441 interchange (k, j), we add "k = j + 1", and we compute D2 the 442 maximal value of the difference. 443 444 Finally, the profitability test is D1 < D2: if in the outer loop 445 the strides are smaller than in the inner loop, then it is 446 profitable to interchange the loops at DEPTH1 and DEPTH2. */ 447 448 static bool 449 lst_interchange_profitable_p (lst_p nest, int depth1, int depth2) 450 { 451 mpz_t d1, d2; 452 bool res; 453 454 gcc_assert (depth1 < depth2); 455 456 mpz_init (d1); 457 mpz_init (d2); 458 459 memory_strides_in_loop (nest, depth1, d1); 460 memory_strides_in_loop (nest, depth2, d2); 461 462 res = mpz_cmp (d1, d2) < 0; 463 464 mpz_clear (d1); 465 mpz_clear (d2); 466 467 return res; 468 } 469 470 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original 471 scattering and assigns the resulting polyhedron to the transformed 472 scattering. */ 473 474 static void 475 pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2, 476 poly_bb_p pbb) 477 { 478 ppl_dimension_type i, dim; 479 ppl_dimension_type *map; 480 ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb); 481 ppl_dimension_type dim1 = psct_dynamic_dim (pbb, depth1); 482 ppl_dimension_type dim2 = psct_dynamic_dim (pbb, depth2); 483 484 ppl_Polyhedron_space_dimension (poly, &dim); 485 map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim); 486 487 for (i = 0; i < dim; i++) 488 map[i] = i; 489 490 map[dim1] = dim2; 491 map[dim2] = dim1; 492 493 ppl_Polyhedron_map_space_dimensions (poly, map, dim); 494 free (map); 495 } 496 497 /* Apply the interchange of loops at depths DEPTH1 and DEPTH2 to all 498 the statements below LST. */ 499 500 static void 501 lst_apply_interchange (lst_p lst, int depth1, int depth2) 502 { 503 if (!lst) 504 return; 505 506 if (LST_LOOP_P (lst)) 507 { 508 int i; 509 lst_p l; 510 511 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l) 512 lst_apply_interchange (l, depth1, depth2); 513 } 514 else 515 pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst)); 516 } 517 518 /* Return true when the nest starting at LOOP1 and ending on LOOP2 is 519 perfect: i.e. there are no sequence of statements. */ 520 521 static bool 522 lst_perfectly_nested_p (lst_p loop1, lst_p loop2) 523 { 524 if (loop1 == loop2) 525 return true; 526 527 if (!LST_LOOP_P (loop1)) 528 return false; 529 530 return VEC_length (lst_p, LST_SEQ (loop1)) == 1 531 && lst_perfectly_nested_p (VEC_index (lst_p, LST_SEQ (loop1), 0), loop2); 532 } 533 534 /* Transform the loop nest between LOOP1 and LOOP2 into a perfect 535 nest. To continue the naming tradition, this function is called 536 after perfect_nestify. NEST is set to the perfectly nested loop 537 that is created. BEFORE/AFTER are set to the loops distributed 538 before/after the loop NEST. */ 539 540 static void 541 lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before, 542 lst_p *nest, lst_p *after) 543 { 544 poly_bb_p first, last; 545 546 gcc_assert (loop1 && loop2 547 && loop1 != loop2 548 && LST_LOOP_P (loop1) && LST_LOOP_P (loop2)); 549 550 first = LST_PBB (lst_find_first_pbb (loop2)); 551 last = LST_PBB (lst_find_last_pbb (loop2)); 552 553 *before = copy_lst (loop1); 554 *nest = copy_lst (loop1); 555 *after = copy_lst (loop1); 556 557 lst_remove_all_before_including_pbb (*before, first, false); 558 lst_remove_all_before_including_pbb (*after, last, true); 559 560 lst_remove_all_before_excluding_pbb (*nest, first, true); 561 lst_remove_all_before_excluding_pbb (*nest, last, false); 562 563 if (lst_empty_p (*before)) 564 { 565 free_lst (*before); 566 *before = NULL; 567 } 568 if (lst_empty_p (*after)) 569 { 570 free_lst (*after); 571 *after = NULL; 572 } 573 if (lst_empty_p (*nest)) 574 { 575 free_lst (*nest); 576 *nest = NULL; 577 } 578 } 579 580 /* Try to interchange LOOP1 with LOOP2 for all the statements of the 581 body of LOOP2. LOOP1 contains LOOP2. Return true if it did the 582 interchange. */ 583 584 static bool 585 lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2) 586 { 587 int depth1 = lst_depth (loop1); 588 int depth2 = lst_depth (loop2); 589 lst_p transformed; 590 591 lst_p before = NULL, nest = NULL, after = NULL; 592 593 if (!lst_perfectly_nested_p (loop1, loop2)) 594 lst_perfect_nestify (loop1, loop2, &before, &nest, &after); 595 596 if (!lst_interchange_profitable_p (loop2, depth1, depth2)) 597 return false; 598 599 lst_apply_interchange (loop2, depth1, depth2); 600 601 /* Sync the transformed LST information and the PBB scatterings 602 before using the scatterings in the data dependence analysis. */ 603 if (before || nest || after) 604 { 605 transformed = lst_substitute_3 (SCOP_TRANSFORMED_SCHEDULE (scop), loop1, 606 before, nest, after); 607 lst_update_scattering (transformed); 608 free_lst (transformed); 609 } 610 611 if (graphite_legal_transform (scop)) 612 { 613 if (dump_file && (dump_flags & TDF_DETAILS)) 614 fprintf (dump_file, 615 "Loops at depths %d and %d will be interchanged.\n", 616 depth1, depth2); 617 618 /* Transform the SCOP_TRANSFORMED_SCHEDULE of the SCOP. */ 619 lst_insert_in_sequence (before, loop1, true); 620 lst_insert_in_sequence (after, loop1, false); 621 622 if (nest) 623 { 624 lst_replace (loop1, nest); 625 free_lst (loop1); 626 } 627 628 return true; 629 } 630 631 /* Undo the transform. */ 632 free_lst (before); 633 free_lst (nest); 634 free_lst (after); 635 lst_apply_interchange (loop2, depth2, depth1); 636 return false; 637 } 638 639 /* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged 640 with the loop OUTER in LST_SEQ (OUTER_FATHER). */ 641 642 static bool 643 lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer, 644 lst_p inner_father) 645 { 646 int inner; 647 lst_p loop1, loop2; 648 649 gcc_assert (outer_father 650 && LST_LOOP_P (outer_father) 651 && LST_LOOP_P (VEC_index (lst_p, LST_SEQ (outer_father), outer)) 652 && inner_father 653 && LST_LOOP_P (inner_father)); 654 655 loop1 = VEC_index (lst_p, LST_SEQ (outer_father), outer); 656 657 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (inner_father), inner, loop2) 658 if (LST_LOOP_P (loop2) 659 && (lst_try_interchange_loops (scop, loop1, loop2) 660 || lst_interchange_select_inner (scop, outer_father, outer, loop2))) 661 return true; 662 663 return false; 664 } 665 666 /* Interchanges all the loops of LOOP and the loops of its body that 667 are considered profitable to interchange. Return the number of 668 interchanged loops. OUTER is the index in LST_SEQ (LOOP) that 669 points to the next outer loop to be considered for interchange. */ 670 671 static int 672 lst_interchange_select_outer (scop_p scop, lst_p loop, int outer) 673 { 674 lst_p l; 675 int res = 0; 676 int i = 0; 677 lst_p father; 678 679 if (!loop || !LST_LOOP_P (loop)) 680 return 0; 681 682 father = LST_LOOP_FATHER (loop); 683 if (father) 684 { 685 while (lst_interchange_select_inner (scop, father, outer, loop)) 686 { 687 res++; 688 loop = VEC_index (lst_p, LST_SEQ (father), outer); 689 } 690 } 691 692 if (LST_LOOP_P (loop)) 693 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), i, l) 694 if (LST_LOOP_P (l)) 695 res += lst_interchange_select_outer (scop, l, i); 696 697 return res; 698 } 699 700 /* Interchanges all the loop depths that are considered profitable for 701 SCOP. Return the number of interchanged loops. */ 702 703 int 704 scop_do_interchange (scop_p scop) 705 { 706 int res = lst_interchange_select_outer 707 (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0); 708 709 lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop)); 710 711 return res; 712 } 713 714 715 #endif 716 717