Mercurial > hg > CbC > CbC_gcc

comparison gcc/graphite-interchange.c @ 67:f6334be47118

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
author nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
date Tue, 22 Mar 2011 17:18:12 +0900
parents b7f97abdc517
children
comparison
equal deleted inserted replaced
65:65488c3d617d 67:f6334be47118
1 /* Interchange heuristics and transform for loop interchange on 1 /* Interchange heuristics and transform for loop interchange on
2 polyhedral representation. 2 polyhedral representation.
3 3
4 Copyright (C) 2009 Free Software Foundation, Inc. 4 Copyright (C) 2009, 2010 Free Software Foundation, Inc.
5 Contributed by Sebastian Pop <sebastian.pop@amd.com> and 5 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
6 Harsha Jagasia <harsha.jagasia@amd.com>. 6 Harsha Jagasia <harsha.jagasia@amd.com>.
7 7
8 This file is part of GCC. 8 This file is part of GCC.
9 9
21 along with GCC; see the file COPYING3. If not see 21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */ 22 <http://www.gnu.org/licenses/>. */
23 #include "config.h" 23 #include "config.h"
24 #include "system.h" 24 #include "system.h"
25 #include "coretypes.h" 25 #include "coretypes.h"
26 #include "tm.h"
27 #include "ggc.h"
28 #include "tree.h"
29 #include "rtl.h"
30 #include "output.h"
31 #include "basic-block.h"
32 #include "diagnostic.h"
33 #include "tree-flow.h" 26 #include "tree-flow.h"
34 #include "toplev.h"
35 #include "tree-dump.h" 27 #include "tree-dump.h"
36 #include "timevar.h"
37 #include "cfgloop.h" 28 #include "cfgloop.h"
38 #include "tree-chrec.h" 29 #include "tree-chrec.h"
39 #include "tree-data-ref.h" 30 #include "tree-data-ref.h"
40 #include "tree-scalar-evolution.h" 31 #include "tree-scalar-evolution.h"
41 #include "tree-pass.h" 32 #include "sese.h"
42 #include "domwalk.h"
43 #include "value-prof.h"
44 #include "pointer-set.h"
45 #include "gimple.h"
46 #include "params.h"
47 33
48 #ifdef HAVE_cloog 34 #ifdef HAVE_cloog
49 #include "cloog/cloog.h"
50 #include "ppl_c.h" 35 #include "ppl_c.h"
51 #include "sese.h"
52 #include "graphite-ppl.h" 36 #include "graphite-ppl.h"
53 #include "graphite.h"
54 #include "graphite-poly.h" 37 #include "graphite-poly.h"
55 38
56 /* Builds a linear expression, of dimension DIM, representing PDR's 39 /* Builds a linear expression, of dimension DIM, representing PDR's
57 memory access: 40 memory access:
58 41
319 302
320 if (dump_file && (dump_flags & TDF_DETAILS)) 303 if (dump_file && (dump_flags & TDF_DETAILS))
321 { 304 {
322 char *str; 305 char *str;
323 void (*gmp_free) (void *, size_t); 306 void (*gmp_free) (void *, size_t);
324 307
325 fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d:", 308 fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d:",
326 pbb_index (pbb), PDR_ID (pdr), (int) depth); 309 pbb_index (pbb), PDR_ID (pdr), (int) depth);
327 str = mpz_get_str (0, 10, stride); 310 str = mpz_get_str (0, 10, stride);
328 fprintf (dump_file, " %s ", str); 311 fprintf (dump_file, " %s ", str);
329 mp_get_memory_functions (NULL, NULL, &gmp_free); 312 mp_get_memory_functions (NULL, NULL, &gmp_free);
348 mpz_t s, n; 331 mpz_t s, n;
349 332
350 mpz_init (s); 333 mpz_init (s);
351 mpz_init (n); 334 mpz_init (n);
352 335
353 for (j = 0; VEC_iterate (lst_p, LST_SEQ (loop), j, l); j++) 336 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), j, l)
354 if (LST_LOOP_P (l)) 337 if (LST_LOOP_P (l))
355 memory_strides_in_loop_1 (l, depth, strides); 338 memory_strides_in_loop_1 (l, depth, strides);
356 else 339 else
357 for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (LST_PBB (l)), i, pdr); i++) 340 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (LST_PBB (l)), i, pdr)
358 { 341 {
359 pdr_stride_in_loop (s, depth, pdr); 342 pdr_stride_in_loop (s, depth, pdr);
360 mpz_set_si (n, PDR_NB_REFS (pdr)); 343 mpz_set_si (n, PDR_NB_REFS (pdr));
361 mpz_mul (s, s, n); 344 mpz_mul (s, s, n);
362 mpz_add (strides, strides, s); 345 mpz_add (strides, strides, s);
461 Finally, the profitability test is D1 < D2: if in the outer loop 444 Finally, the profitability test is D1 < D2: if in the outer loop
462 the strides are smaller than in the inner loop, then it is 445 the strides are smaller than in the inner loop, then it is
463 profitable to interchange the loops at DEPTH1 and DEPTH2. */ 446 profitable to interchange the loops at DEPTH1 and DEPTH2. */
464 447
465 static bool 448 static bool
466 lst_interchange_profitable_p (lst_p loop1, lst_p loop2) 449 lst_interchange_profitable_p (lst_p nest, int depth1, int depth2)
467 { 450 {
468 mpz_t d1, d2; 451 mpz_t d1, d2;
469 bool res; 452 bool res;
470 453
471 gcc_assert (loop1 && loop2 454 gcc_assert (depth1 < depth2);
472 && LST_LOOP_P (loop1) && LST_LOOP_P (loop2)
473 && lst_depth (loop1) < lst_depth (loop2));
474 455
475 mpz_init (d1); 456 mpz_init (d1);
476 mpz_init (d2); 457 mpz_init (d2);
477 458
478 memory_strides_in_loop (loop1, lst_depth (loop1), d1); 459 memory_strides_in_loop (nest, depth1, d1);
479 memory_strides_in_loop (loop2, lst_depth (loop2), d2); 460 memory_strides_in_loop (nest, depth2, d2);
480 461
481 res = value_lt (d1, d2); 462 res = mpz_cmp (d1, d2) < 0;
482 463
483 mpz_clear (d1); 464 mpz_clear (d1);
484 mpz_clear (d2); 465 mpz_clear (d2);
485 466
486 return res; 467 return res;
525 if (LST_LOOP_P (lst)) 506 if (LST_LOOP_P (lst))
526 { 507 {
527 int i; 508 int i;
528 lst_p l; 509 lst_p l;
529 510
530 for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) 511 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
531 lst_apply_interchange (l, depth1, depth2); 512 lst_apply_interchange (l, depth1, depth2);
532 } 513 }
533 else 514 else
534 pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst)); 515 pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst));
535 } 516 }
607 int depth2 = lst_depth (loop2); 588 int depth2 = lst_depth (loop2);
608 lst_p transformed; 589 lst_p transformed;
609 590
610 lst_p before = NULL, nest = NULL, after = NULL; 591 lst_p before = NULL, nest = NULL, after = NULL;
611 592
612 if (!lst_interchange_profitable_p (loop1, loop2))
613 return false;
614
615 if (!lst_perfectly_nested_p (loop1, loop2)) 593 if (!lst_perfectly_nested_p (loop1, loop2))
616 lst_perfect_nestify (loop1, loop2, &before, &nest, &after); 594 lst_perfect_nestify (loop1, loop2, &before, &nest, &after);
595
596 if (!lst_interchange_profitable_p (loop2, depth1, depth2))
597 return false;
617 598
618 lst_apply_interchange (loop2, depth1, depth2); 599 lst_apply_interchange (loop2, depth1, depth2);
619 600
620 /* Sync the transformed LST information and the PBB scatterings 601 /* Sync the transformed LST information and the PBB scatterings
621 before using the scatterings in the data dependence analysis. */ 602 before using the scatterings in the data dependence analysis. */
671 && inner_father 652 && inner_father
672 && LST_LOOP_P (inner_father)); 653 && LST_LOOP_P (inner_father));
673 654
674 loop1 = VEC_index (lst_p, LST_SEQ (outer_father), outer); 655 loop1 = VEC_index (lst_p, LST_SEQ (outer_father), outer);
675 656
676 for (inner = 0; VEC_iterate (lst_p, LST_SEQ (inner_father), inner, loop2); inner++) 657 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (inner_father), inner, loop2)
677 if (LST_LOOP_P (loop2) 658 if (LST_LOOP_P (loop2)
678 && (lst_try_interchange_loops (scop, loop1, loop2) 659 && (lst_try_interchange_loops (scop, loop1, loop2)
679 || lst_interchange_select_inner (scop, outer_father, outer, loop2))) 660 || lst_interchange_select_inner (scop, outer_father, outer, loop2)))
680 return true; 661 return true;
681 662
707 loop = VEC_index (lst_p, LST_SEQ (father), outer); 688 loop = VEC_index (lst_p, LST_SEQ (father), outer);
708 } 689 }
709 } 690 }
710 691
711 if (LST_LOOP_P (loop)) 692 if (LST_LOOP_P (loop))
712 for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l); i++) 693 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), i, l)
713 if (LST_LOOP_P (l)) 694 if (LST_LOOP_P (l))
714 res |= lst_interchange_select_outer (scop, l, i); 695 res |= lst_interchange_select_outer (scop, l, i);
715 696
716 return res; 697 return res;
717 } 698 }