1 /* Interchange heuristics and transform for loop interchange on
2 polyhedral representation.
4 Copyright (C) 2009 Free Software Foundation, Inc.
5 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
6 Harsha Jagasia <harsha.jagasia@amd.com>.
8 This file is part of GCC.
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)
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.
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/>. */
25 #include "coretypes.h"
31 #include "basic-block.h"
32 #include "diagnostic.h"
33 #include "tree-flow.h"
35 #include "tree-dump.h"
38 #include "tree-chrec.h"
39 #include "tree-data-ref.h"
40 #include "tree-scalar-evolution.h"
41 #include "tree-pass.h"
43 #include "value-prof.h"
44 #include "pointer-set.h"
49 #include "cloog/cloog.h"
52 #include "graphite-ppl.h"
54 #include "graphite-poly.h"
56 /* Computes ACCESS_STRIDES, the sum of all the strides of PDR at
60 gather_access_strides (poly_dr_p pdr ATTRIBUTE_UNUSED
,
61 graphite_dim_t loop_depth ATTRIBUTE_UNUSED
,
62 Value access_strides ATTRIBUTE_UNUSED
)
67 /* Returns true when it is profitable to interchange loop at depth1
68 and loop at depth2 with depth1 < depth2 for the polyhedral black
72 pbb_interchange_profitable_p (graphite_dim_t depth1
, graphite_dim_t depth2
, poly_bb_p pbb
)
76 Value access_strides1
, access_strides2
;
79 gcc_assert (depth1
< depth2
);
81 value_init (access_strides1
);
82 value_init (access_strides2
);
84 value_set_si (access_strides1
, 0);
85 value_set_si (access_strides2
, 0);
87 for (i
= 0; VEC_iterate (poly_dr_p
, PBB_DRS (pbb
), i
, pdr
); i
++)
89 gather_access_strides (pdr
, depth1
, access_strides1
);
90 gather_access_strides (pdr
, depth2
, access_strides2
);
93 res
= value_lt (access_strides1
, access_strides2
);
95 value_clear (access_strides1
);
96 value_clear (access_strides2
);
101 /* Interchanges the loops at DEPTH1 and DEPTH2 of the original
102 scattering and assigns the resulting polyhedron to the transformed
106 pbb_interchange_loop_depths (graphite_dim_t depth1
, graphite_dim_t depth2
, poly_bb_p pbb
)
108 ppl_dimension_type i
, dim
;
109 ppl_dimension_type
*map
;
110 ppl_Polyhedron_t poly
= PBB_TRANSFORMED_SCATTERING (pbb
);
111 ppl_dimension_type dim1
= psct_iterator_dim (pbb
, depth1
);
112 ppl_dimension_type dim2
= psct_iterator_dim (pbb
, depth2
);
114 ppl_Polyhedron_space_dimension (poly
, &dim
);
115 map
= (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
117 for (i
= 0; i
< dim
; i
++)
123 ppl_Polyhedron_map_space_dimensions (poly
, map
, dim
);
127 /* Interchanges all the loop depths that are considered profitable for PBB. */
130 pbb_do_interchange (poly_bb_p pbb
, scop_p scop
)
133 bool transform_done
= false;
135 for (i
= 0; i
< pbb_dim_iter_domain (pbb
); i
++)
136 for (j
= i
+ 1; j
< pbb_dim_iter_domain (pbb
); j
++)
137 if (pbb_interchange_profitable_p (i
, j
, pbb
))
139 pbb_interchange_loop_depths (i
, j
, pbb
);
141 if (graphite_legal_transform (scop
))
143 transform_done
= true;
145 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
147 "PBB %d: loops at depths %d and %d will be interchanged.\n",
148 GBB_BB (PBB_BLACK_BOX (pbb
))->index
, (int) i
, (int) j
);
151 /* Undo the transform. */
152 pbb_interchange_loop_depths (j
, i
, pbb
);
155 return transform_done
;
158 /* Interchanges all the loop depths that are considered profitable for SCOP. */
161 scop_do_interchange (scop_p scop
)
165 bool transform_done
= false;
167 store_scattering (scop
);
169 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
170 transform_done
|= pbb_do_interchange (pbb
, scop
);
175 if (!graphite_legal_transform (scop
))
177 restore_scattering (scop
);
181 return transform_done
;