]>
Commit | Line | Data |
---|---|---|
2abae5f1 | 1 | /* Conversion of SESE regions to Polyhedra. |
5624e564 | 2 | Copyright (C) 2009-2015 Free Software Foundation, Inc. |
2abae5f1 SP |
3 | Contributed by Sebastian Pop <sebastian.pop@amd.com>. |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 3, or (at your option) | |
10 | any later version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GCC; see the file COPYING3. If not see | |
19 | <http://www.gnu.org/licenses/>. */ | |
20 | ||
4d776011 DE |
21 | #define USES_ISL |
22 | ||
2abae5f1 | 23 | #include "config.h" |
33ad93b9 | 24 | |
eae1a5d4 | 25 | #ifdef HAVE_isl |
33ad93b9 | 26 | |
2abae5f1 SP |
27 | #include "system.h" |
28 | #include "coretypes.h" | |
c7131fb2 | 29 | #include "backend.h" |
9fdcd34e | 30 | #include "cfghooks.h" |
40e23961 | 31 | #include "tree.h" |
c7131fb2 | 32 | #include "gimple.h" |
c7131fb2 | 33 | #include "ssa.h" |
49b8fe6c | 34 | #include "params.h" |
40e23961 | 35 | #include "fold-const.h" |
5be5c238 | 36 | #include "gimple-iterator.h" |
18f429e2 AM |
37 | #include "gimplify.h" |
38 | #include "gimplify-me.h" | |
442b4905 | 39 | #include "tree-cfg.h" |
e28030cf AM |
40 | #include "tree-ssa-loop-manip.h" |
41 | #include "tree-ssa-loop-niter.h" | |
442b4905 AM |
42 | #include "tree-ssa-loop.h" |
43 | #include "tree-into-ssa.h" | |
7a1c57d3 | 44 | #include "tree-pass.h" |
2abae5f1 | 45 | #include "cfgloop.h" |
2abae5f1 SP |
46 | #include "tree-data-ref.h" |
47 | #include "tree-scalar-evolution.h" | |
2abae5f1 | 48 | #include "domwalk.h" |
9c358739 | 49 | #include "tree-ssa-propagate.h" |
4d776011 DE |
50 | |
51 | #include <isl/constraint.h> | |
52 | #include <isl/set.h> | |
53 | #include <isl/map.h> | |
54 | #include <isl/union_map.h> | |
55 | #include <isl/constraint.h> | |
56 | #include <isl/aff.h> | |
57 | #include <isl/val.h> | |
58 | ||
59 | /* Since ISL-0.13, the extern is in val_gmp.h. */ | |
60 | #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus) | |
61 | extern "C" { | |
62 | #endif | |
63 | #include <isl/val_gmp.h> | |
64 | #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus) | |
65 | } | |
66 | #endif | |
67 | ||
68 | #include "graphite-poly.h" | |
2abae5f1 | 69 | |
33ad93b9 RG |
70 | /* Assigns to RES the value of the INTEGER_CST T. */ |
71 | ||
72 | static inline void | |
73 | tree_int_to_gmp (tree t, mpz_t res) | |
74 | { | |
807e902e | 75 | wi::to_mpz (t, res, TYPE_SIGN (TREE_TYPE (t))); |
33ad93b9 RG |
76 | } |
77 | ||
33ad93b9 RG |
78 | /* Return an ISL identifier for the polyhedral basic block PBB. */ |
79 | ||
80 | static isl_id * | |
81 | isl_id_for_pbb (scop_p s, poly_bb_p pbb) | |
82 | { | |
1b38d3ec | 83 | char name[10]; |
33ad93b9 | 84 | snprintf (name, sizeof (name), "S_%d", pbb_index (pbb)); |
8e4dc590 | 85 | return isl_id_alloc (s->isl_context, name, pbb); |
33ad93b9 RG |
86 | } |
87 | ||
2abae5f1 SP |
88 | /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron. |
89 | We generate SCATTERING_DIMENSIONS scattering dimensions. | |
90 | ||
2abae5f1 SP |
91 | The scattering polyhedron consists of these dimensions: scattering, |
92 | loop_iterators, parameters. | |
93 | ||
94 | Example: | |
95 | ||
96 | | scattering_dimensions = 5 | |
2abae5f1 SP |
97 | | nb_iterators = 1 |
98 | | scop_nb_params = 2 | |
99 | | | |
100 | | Schedule: | |
101 | | i | |
102 | | 4 5 | |
103 | | | |
104 | | Scattering polyhedron: | |
105 | | | |
106 | | scattering: {s1, s2, s3, s4, s5} | |
107 | | loop_iterators: {i} | |
108 | | parameters: {p1, p2} | |
109 | | | |
110 | | s1 s2 s3 s4 s5 i p1 p2 1 | |
111 | | 1 0 0 0 0 0 0 0 -4 = 0 | |
112 | | 0 1 0 0 0 -1 0 0 0 = 0 | |
113 | | 0 0 1 0 0 0 0 0 -5 = 0 */ | |
114 | ||
115 | static void | |
504fbc11 AZ |
116 | build_pbb_minimal_scattering_polyhedrons (isl_aff *static_sched, poly_bb_p pbb, |
117 | int *sequence_dims, | |
118 | int nb_sequence_dim) | |
2abae5f1 | 119 | { |
504fbc11 AZ |
120 | int local_dim = isl_set_dim (pbb->domain, isl_dim_set); |
121 | ||
122 | /* Remove a sequence dimension if irrelevant to domain of current pbb. */ | |
123 | int actual_nb_dim = 0; | |
124 | for (int i = 0; i < nb_sequence_dim; i++) | |
125 | if (sequence_dims[i] <= local_dim) | |
126 | actual_nb_dim++; | |
127 | ||
128 | /* Build an array that combines sequence dimensions and loops dimensions info. | |
129 | This is used later to compute the static scattering polyhedrons. */ | |
130 | bool *sequence_and_loop_dims = NULL; | |
131 | if (local_dim + actual_nb_dim > 0) | |
132 | { | |
133 | sequence_and_loop_dims = XNEWVEC (bool, local_dim + actual_nb_dim); | |
2abae5f1 | 134 | |
504fbc11 AZ |
135 | int i = 0, j = 0; |
136 | for (; i < local_dim; i++) | |
137 | { | |
138 | if (sequence_dims && sequence_dims[j] == i) | |
139 | { | |
140 | /* True for sequence dimension. */ | |
141 | sequence_and_loop_dims[i + j] = true; | |
142 | j++; | |
143 | } | |
144 | /* False for loop dimension. */ | |
145 | sequence_and_loop_dims[i + j] = false; | |
146 | } | |
147 | /* Fake loops make things shifted by one. */ | |
148 | if (sequence_dims && sequence_dims[j] == i) | |
149 | sequence_and_loop_dims[i + j] = true; | |
150 | } | |
2abae5f1 | 151 | |
504fbc11 | 152 | int scattering_dimensions = local_dim + actual_nb_dim; |
8e4dc590 | 153 | isl_space *dc = isl_set_get_space (pbb->domain); |
504fbc11 AZ |
154 | isl_space *dm = isl_space_add_dims (isl_space_from_domain (dc), isl_dim_out, |
155 | scattering_dimensions); | |
33ad93b9 | 156 | pbb->schedule = isl_map_universe (dm); |
2abae5f1 | 157 | |
504fbc11 | 158 | int k = 0; |
8e4dc590 | 159 | for (int i = 0; i < scattering_dimensions; i++) |
2abae5f1 | 160 | { |
504fbc11 | 161 | if (!sequence_and_loop_dims[i]) |
2abae5f1 | 162 | { |
504fbc11 AZ |
163 | /* Iterations of this loop - loop dimension. */ |
164 | pbb->schedule = isl_map_equate (pbb->schedule, isl_dim_in, k, | |
33ad93b9 | 165 | isl_dim_out, i); |
504fbc11 AZ |
166 | k++; |
167 | continue; | |
2abae5f1 | 168 | } |
504fbc11 AZ |
169 | |
170 | /* Textual order inside this loop - sequence dimension. */ | |
171 | isl_space *s = isl_map_get_space (pbb->schedule); | |
172 | isl_local_space *ls = isl_local_space_from_space (s); | |
173 | isl_constraint *c = isl_equality_alloc (ls); | |
174 | isl_val *val = isl_aff_get_coefficient_val (static_sched, isl_dim_in, k); | |
175 | gcc_assert (val && isl_val_is_int (val)); | |
176 | val = isl_val_neg (val); | |
177 | c = isl_constraint_set_constant_val (c, val); | |
178 | c = isl_constraint_set_coefficient_si (c, isl_dim_out, i, 1); | |
179 | pbb->schedule = isl_map_add_constraint (pbb->schedule, c); | |
2abae5f1 SP |
180 | } |
181 | ||
504fbc11 | 182 | XDELETEVEC (sequence_and_loop_dims); |
33ad93b9 | 183 | pbb->transformed = isl_map_copy (pbb->schedule); |
2abae5f1 SP |
184 | } |
185 | ||
504fbc11 AZ |
186 | /* Build the static schedule for BB. This function minimizes the number of |
187 | dimensions used for pbb sequences. | |
2abae5f1 SP |
188 | |
189 | The following example informally defines the static schedule: | |
190 | ||
191 | A | |
192 | for (i: ...) | |
193 | { | |
194 | for (j: ...) | |
504fbc11 AZ |
195 | { |
196 | B | |
197 | C | |
198 | } | |
199 | } | |
200 | for (i: ...) | |
201 | { | |
2abae5f1 | 202 | for (k: ...) |
504fbc11 AZ |
203 | { |
204 | D | |
205 | E | |
206 | } | |
2abae5f1 SP |
207 | } |
208 | F | |
209 | ||
210 | Static schedules for A to F: | |
211 | ||
504fbc11 AZ |
212 | A (0) |
213 | B (1 i0 i1 0) | |
214 | C (1 i0 i1 1) | |
215 | D (2 i0 i1 2) | |
216 | E (2 i0 i1 3) | |
217 | F (3) | |
2abae5f1 SP |
218 | */ |
219 | ||
220 | static void | |
504fbc11 | 221 | build_scop_minimal_scattering (scop_p scop) |
2abae5f1 | 222 | { |
65ef70d6 | 223 | gimple_poly_bb_p previous_gbb = NULL; |
504fbc11 AZ |
224 | int *temp_for_sequence_dims = NULL; |
225 | int i; | |
226 | poly_bb_p pbb; | |
227 | ||
228 | /* Go through the pbbs to determine the minimum number of dimensions needed to | |
229 | build the static schedule. */ | |
230 | int nb_dims = 0; | |
231 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) | |
232 | { | |
233 | int dim = isl_set_dim (pbb->domain, isl_dim_set); | |
234 | if (dim > nb_dims) | |
235 | nb_dims = dim; | |
236 | } | |
237 | ||
238 | /* One extra dimension for the outer fake loop. */ | |
239 | nb_dims++; | |
240 | temp_for_sequence_dims = XCNEWVEC (int, nb_dims); | |
2abae5f1 | 241 | |
504fbc11 AZ |
242 | /* Record the number of common loops for each dimension. */ |
243 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) | |
244 | { | |
245 | gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); | |
246 | int prefix = 0; | |
247 | ||
248 | if (previous_gbb) | |
249 | { | |
250 | prefix = nb_common_loops (scop->scop_info->region, previous_gbb, gbb); | |
251 | temp_for_sequence_dims[prefix] += 1; | |
252 | } | |
253 | previous_gbb = gbb; | |
254 | } | |
255 | ||
256 | /* Analyze the info in temp_for_sequence_dim and determine the minimal number | |
257 | of sequence dimensions. A dimension that did not appear as common | |
258 | dimension should not be considered as a sequence dimension. */ | |
259 | int nb_sequence_params = 0; | |
260 | for (i = 0; i < nb_dims; i++) | |
261 | if (temp_for_sequence_dims[i] > 0) | |
262 | nb_sequence_params++; | |
263 | ||
264 | int *sequence_dims = NULL; | |
265 | if (nb_sequence_params > 0) | |
266 | { | |
267 | int j = 0; | |
268 | sequence_dims = XNEWVEC (int, nb_sequence_params); | |
269 | for (i = 0; i < nb_dims; i++) | |
270 | if (temp_for_sequence_dims[i] > 0) | |
271 | { | |
272 | sequence_dims[j] = i; | |
273 | j++; | |
274 | } | |
275 | } | |
276 | ||
277 | XDELETEVEC (temp_for_sequence_dims); | |
278 | ||
279 | isl_space *dc = isl_set_get_space (scop->param_context); | |
0fc822d0 | 280 | dc = isl_space_add_dims (dc, isl_dim_set, number_of_loops (cfun)); |
504fbc11 AZ |
281 | isl_local_space *local_space = isl_local_space_from_space (dc); |
282 | isl_aff *static_sched = isl_aff_zero_on_domain (local_space); | |
2abae5f1 SP |
283 | |
284 | /* We have to start schedules at 0 on the first component and | |
285 | because we cannot compare_prefix_loops against a previous loop, | |
286 | prefix will be equal to zero, and that index will be | |
287 | incremented before copying. */ | |
33ad93b9 | 288 | static_sched = isl_aff_add_coefficient_si (static_sched, isl_dim_in, 0, -1); |
2abae5f1 | 289 | |
504fbc11 | 290 | previous_gbb = NULL; |
b0b5710c | 291 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) |
2abae5f1 | 292 | { |
65ef70d6 | 293 | gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); |
8e4dc590 | 294 | int prefix = 0; |
2abae5f1 SP |
295 | |
296 | if (previous_gbb) | |
d37fc3aa | 297 | prefix = nb_common_loops (scop->scop_info->region, previous_gbb, gbb); |
2abae5f1 SP |
298 | |
299 | previous_gbb = gbb; | |
2abae5f1 | 300 | |
33ad93b9 RG |
301 | static_sched = isl_aff_add_coefficient_si (static_sched, isl_dim_in, |
302 | prefix, 1); | |
504fbc11 AZ |
303 | build_pbb_minimal_scattering_polyhedrons (static_sched, pbb, |
304 | sequence_dims, nb_sequence_params); | |
33ad93b9 RG |
305 | } |
306 | ||
504fbc11 | 307 | XDELETEVEC (sequence_dims); |
33ad93b9 RG |
308 | isl_aff_free (static_sched); |
309 | } | |
310 | ||
0473915e AZ |
311 | /* Build the original schedule showing the orginal order of execution |
312 | of statement instances. | |
313 | ||
314 | The following example shows the original schedule: | |
315 | ||
316 | for (i: ...) | |
317 | { | |
318 | for (j: ...) | |
319 | { | |
320 | A | |
321 | } | |
322 | B | |
323 | } | |
324 | C | |
325 | for (i: ...) | |
326 | { | |
327 | D | |
328 | } | |
329 | ||
330 | Static schedules for A to D expressed in a union map: | |
eefa4baf AZ |
331 | { |
332 | S_A[i0, i1] -> [0, i0, 0, i1]; | |
333 | S_B[i0] -> [0, i0, 1]; | |
334 | S_C[] -> [1]; | |
335 | S_D[i0] -> [2, i0, 0] | |
336 | } | |
0473915e AZ |
337 | */ |
338 | ||
339 | static void | |
340 | build_scop_original_schedule (scop_p scop) | |
341 | { | |
eefa4baf AZ |
342 | int i; |
343 | poly_bb_p pbb; | |
344 | ||
0473915e AZ |
345 | isl_space *space = isl_set_get_space (scop->param_context); |
346 | isl_union_map *res = isl_union_map_empty (space); | |
347 | ||
0473915e | 348 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) |
eefa4baf AZ |
349 | res = isl_union_map_add_map (res, isl_map_copy (pbb->schedule)); |
350 | ||
0473915e AZ |
351 | scop->original_schedule = res; |
352 | } | |
353 | ||
354 | ||
33ad93b9 RG |
355 | static isl_pw_aff *extract_affine (scop_p, tree, __isl_take isl_space *space); |
356 | ||
357 | /* Extract an affine expression from the chain of recurrence E. */ | |
2abae5f1 | 358 | |
33ad93b9 RG |
359 | static isl_pw_aff * |
360 | extract_affine_chrec (scop_p s, tree e, __isl_take isl_space *space) | |
361 | { | |
362 | isl_pw_aff *lhs = extract_affine (s, CHREC_LEFT (e), isl_space_copy (space)); | |
363 | isl_pw_aff *rhs = extract_affine (s, CHREC_RIGHT (e), isl_space_copy (space)); | |
364 | isl_local_space *ls = isl_local_space_from_space (space); | |
d37fc3aa | 365 | unsigned pos = sese_loop_depth (s->scop_info->region, get_chrec_loop (e)) - 1; |
33ad93b9 RG |
366 | isl_aff *loop = isl_aff_set_coefficient_si |
367 | (isl_aff_zero_on_domain (ls), isl_dim_in, pos, 1); | |
368 | isl_pw_aff *l = isl_pw_aff_from_aff (loop); | |
369 | ||
370 | /* Before multiplying, make sure that the result is affine. */ | |
371 | gcc_assert (isl_pw_aff_is_cst (rhs) | |
372 | || isl_pw_aff_is_cst (l)); | |
373 | ||
374 | return isl_pw_aff_add (lhs, isl_pw_aff_mul (rhs, l)); | |
375 | } | |
376 | ||
377 | /* Extract an affine expression from the mult_expr E. */ | |
378 | ||
379 | static isl_pw_aff * | |
380 | extract_affine_mul (scop_p s, tree e, __isl_take isl_space *space) | |
381 | { | |
382 | isl_pw_aff *lhs = extract_affine (s, TREE_OPERAND (e, 0), | |
383 | isl_space_copy (space)); | |
384 | isl_pw_aff *rhs = extract_affine (s, TREE_OPERAND (e, 1), space); | |
2abae5f1 | 385 | |
33ad93b9 RG |
386 | if (!isl_pw_aff_is_cst (lhs) |
387 | && !isl_pw_aff_is_cst (rhs)) | |
388 | { | |
389 | isl_pw_aff_free (lhs); | |
390 | isl_pw_aff_free (rhs); | |
391 | return NULL; | |
2abae5f1 SP |
392 | } |
393 | ||
33ad93b9 | 394 | return isl_pw_aff_mul (lhs, rhs); |
2abae5f1 SP |
395 | } |
396 | ||
33ad93b9 | 397 | /* Return an ISL identifier from the name of the ssa_name E. */ |
2abae5f1 | 398 | |
33ad93b9 RG |
399 | static isl_id * |
400 | isl_id_for_ssa_name (scop_p s, tree e) | |
2abae5f1 | 401 | { |
33ad93b9 RG |
402 | const char *name = get_name (e); |
403 | isl_id *id; | |
404 | ||
405 | if (name) | |
8e4dc590 | 406 | id = isl_id_alloc (s->isl_context, name, e); |
33ad93b9 RG |
407 | else |
408 | { | |
1b38d3ec | 409 | char name1[10]; |
33ad93b9 | 410 | snprintf (name1, sizeof (name1), "P_%d", SSA_NAME_VERSION (e)); |
8e4dc590 | 411 | id = isl_id_alloc (s->isl_context, name1, e); |
33ad93b9 | 412 | } |
2abae5f1 | 413 | |
33ad93b9 RG |
414 | return id; |
415 | } | |
2abae5f1 | 416 | |
65b016eb AK |
417 | /* Return an ISL identifier for the data reference DR. Data references and |
418 | scalar references get the same isl_id. They need to be comparable and are | |
419 | distinguished through the first dimension, which contains the alias set or | |
420 | SSA_NAME_VERSION number. */ | |
2abae5f1 | 421 | |
33ad93b9 | 422 | static isl_id * |
65b016eb | 423 | isl_id_for_dr (scop_p s) |
33ad93b9 | 424 | { |
8e4dc590 | 425 | return isl_id_alloc (s->isl_context, "", 0); |
2abae5f1 SP |
426 | } |
427 | ||
33ad93b9 | 428 | /* Extract an affine expression from the ssa_name E. */ |
2abae5f1 | 429 | |
33ad93b9 RG |
430 | static isl_pw_aff * |
431 | extract_affine_name (scop_p s, tree e, __isl_take isl_space *space) | |
2abae5f1 | 432 | { |
8e4dc590 AK |
433 | isl_id *id = isl_id_for_ssa_name (s, e); |
434 | int dimension = isl_space_find_dim_by_id (space, isl_dim_param, id); | |
c3284718 | 435 | isl_id_free (id); |
8e4dc590 AK |
436 | isl_set *dom = isl_set_universe (isl_space_copy (space)); |
437 | isl_aff *aff = isl_aff_zero_on_domain (isl_local_space_from_space (space)); | |
33ad93b9 RG |
438 | aff = isl_aff_add_coefficient_si (aff, isl_dim_param, dimension, 1); |
439 | return isl_pw_aff_alloc (dom, aff); | |
440 | } | |
2abae5f1 | 441 | |
33ad93b9 | 442 | /* Extract an affine expression from the gmp constant G. */ |
2abae5f1 | 443 | |
33ad93b9 RG |
444 | static isl_pw_aff * |
445 | extract_affine_gmp (mpz_t g, __isl_take isl_space *space) | |
446 | { | |
447 | isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space)); | |
448 | isl_aff *aff = isl_aff_zero_on_domain (ls); | |
449 | isl_set *dom = isl_set_universe (space); | |
8e4dc590 AK |
450 | isl_ctx *ct = isl_aff_get_ctx (aff); |
451 | isl_val *v = isl_val_int_from_gmp (ct, g); | |
b47595f7 | 452 | aff = isl_aff_add_constant_val (aff, v); |
2abae5f1 | 453 | |
33ad93b9 | 454 | return isl_pw_aff_alloc (dom, aff); |
2abae5f1 SP |
455 | } |
456 | ||
33ad93b9 | 457 | /* Extract an affine expression from the integer_cst E. */ |
2abae5f1 | 458 | |
33ad93b9 RG |
459 | static isl_pw_aff * |
460 | extract_affine_int (tree e, __isl_take isl_space *space) | |
461 | { | |
33ad93b9 RG |
462 | mpz_t g; |
463 | ||
464 | mpz_init (g); | |
465 | tree_int_to_gmp (e, g); | |
8e4dc590 | 466 | isl_pw_aff *res = extract_affine_gmp (g, space); |
33ad93b9 RG |
467 | mpz_clear (g); |
468 | ||
469 | return res; | |
470 | } | |
471 | ||
472 | /* Compute pwaff mod 2^width. */ | |
473 | ||
474 | static isl_pw_aff * | |
475 | wrap (isl_pw_aff *pwaff, unsigned width) | |
2abae5f1 | 476 | { |
b47595f7 | 477 | isl_val *mod; |
2abae5f1 | 478 | |
24757752 | 479 | mod = isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff), width); |
b47595f7 MN |
480 | mod = isl_val_2exp (mod); |
481 | pwaff = isl_pw_aff_mod_val (pwaff, mod); | |
33ad93b9 RG |
482 | |
483 | return pwaff; | |
2abae5f1 SP |
484 | } |
485 | ||
2abae5f1 SP |
486 | /* When parameter NAME is in REGION, returns its index in SESE_PARAMS. |
487 | Otherwise returns -1. */ | |
488 | ||
489 | static inline int | |
bafcb153 | 490 | parameter_index_in_region_1 (tree name, sese_info_p region) |
2abae5f1 SP |
491 | { |
492 | int i; | |
493 | tree p; | |
494 | ||
495 | gcc_assert (TREE_CODE (name) == SSA_NAME); | |
496 | ||
65b016eb | 497 | FOR_EACH_VEC_ELT (region->params, i, p) |
2abae5f1 SP |
498 | if (p == name) |
499 | return i; | |
500 | ||
501 | return -1; | |
502 | } | |
503 | ||
33ad93b9 | 504 | /* Extract an affine expression from the tree E in the scop S. */ |
2abae5f1 | 505 | |
33ad93b9 RG |
506 | static isl_pw_aff * |
507 | extract_affine (scop_p s, tree e, __isl_take isl_space *space) | |
2abae5f1 | 508 | { |
33ad93b9 | 509 | isl_pw_aff *lhs, *rhs, *res; |
33ad93b9 RG |
510 | |
511 | if (e == chrec_dont_know) { | |
512 | isl_space_free (space); | |
513 | return NULL; | |
514 | } | |
2abae5f1 SP |
515 | |
516 | switch (TREE_CODE (e)) | |
517 | { | |
518 | case POLYNOMIAL_CHREC: | |
33ad93b9 | 519 | res = extract_affine_chrec (s, e, space); |
2abae5f1 SP |
520 | break; |
521 | ||
522 | case MULT_EXPR: | |
33ad93b9 | 523 | res = extract_affine_mul (s, e, space); |
2abae5f1 SP |
524 | break; |
525 | ||
526 | case PLUS_EXPR: | |
527 | case POINTER_PLUS_EXPR: | |
33ad93b9 RG |
528 | lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); |
529 | rhs = extract_affine (s, TREE_OPERAND (e, 1), space); | |
530 | res = isl_pw_aff_add (lhs, rhs); | |
2abae5f1 SP |
531 | break; |
532 | ||
533 | case MINUS_EXPR: | |
33ad93b9 RG |
534 | lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); |
535 | rhs = extract_affine (s, TREE_OPERAND (e, 1), space); | |
536 | res = isl_pw_aff_sub (lhs, rhs); | |
537 | break; | |
2abae5f1 SP |
538 | |
539 | case NEGATE_EXPR: | |
33ad93b9 RG |
540 | case BIT_NOT_EXPR: |
541 | lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); | |
542 | rhs = extract_affine (s, integer_minus_one_node, space); | |
543 | res = isl_pw_aff_mul (lhs, rhs); | |
544 | break; | |
2abae5f1 | 545 | |
33ad93b9 | 546 | case SSA_NAME: |
d37fc3aa | 547 | gcc_assert (-1 != parameter_index_in_region_1 (e, s->scop_info) |
78fd2726 | 548 | || !invariant_in_sese_p_rec (e, s->scop_info->region, NULL)); |
33ad93b9 RG |
549 | res = extract_affine_name (s, e, space); |
550 | break; | |
2abae5f1 | 551 | |
33ad93b9 RG |
552 | case INTEGER_CST: |
553 | res = extract_affine_int (e, space); | |
554 | /* No need to wrap a single integer. */ | |
555 | return res; | |
2abae5f1 | 556 | |
33ad93b9 RG |
557 | CASE_CONVERT: |
558 | case NON_LVALUE_EXPR: | |
559 | res = extract_affine (s, TREE_OPERAND (e, 0), space); | |
560 | break; | |
2abae5f1 | 561 | |
33ad93b9 RG |
562 | default: |
563 | gcc_unreachable (); | |
564 | break; | |
565 | } | |
2abae5f1 | 566 | |
8e4dc590 | 567 | tree type = TREE_TYPE (e); |
33ad93b9 RG |
568 | if (TYPE_UNSIGNED (type)) |
569 | res = wrap (res, TYPE_PRECISION (type)); | |
2abae5f1 | 570 | |
33ad93b9 RG |
571 | return res; |
572 | } | |
2abae5f1 | 573 | |
076d564d | 574 | /* Assign dimension for each parameter in SCOP. */ |
a5a59b11 | 575 | |
076d564d AK |
576 | static void |
577 | set_scop_parameter_dim (scop_p scop) | |
578 | { | |
d37fc3aa | 579 | sese_info_p region = scop->scop_info; |
076d564d | 580 | unsigned nbp = sese_nb_params (region); |
8e4dc590 | 581 | isl_space *space = isl_space_set_alloc (scop->isl_context, nbp, 0); |
a5a59b11 | 582 | |
076d564d AK |
583 | unsigned i; |
584 | tree e; | |
65b016eb | 585 | FOR_EACH_VEC_ELT (region->params, i, e) |
076d564d AK |
586 | space = isl_space_set_dim_id (space, isl_dim_param, i, |
587 | isl_id_for_ssa_name (scop, e)); | |
588 | ||
8e4dc590 | 589 | scop->param_context = isl_set_universe (space); |
a5a59b11 SP |
590 | } |
591 | ||
36f40be0 AK |
592 | static inline bool |
593 | cleanup_loop_iter_dom (isl_set *inner, isl_set *outer, isl_space *space, mpz_t g) | |
594 | { | |
595 | isl_set_free (inner); | |
596 | isl_set_free (outer); | |
597 | isl_space_free (space); | |
598 | mpz_clear (g); | |
599 | return false; | |
600 | } | |
601 | ||
2abae5f1 SP |
602 | /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives |
603 | the constraints for the surrounding loops. */ | |
604 | ||
36f40be0 | 605 | static bool |
2abae5f1 | 606 | build_loop_iteration_domains (scop_p scop, struct loop *loop, |
33ad93b9 RG |
607 | int nb, |
608 | isl_set *outer, isl_set **doms) | |
2abae5f1 | 609 | { |
8e4dc590 | 610 | |
2abae5f1 | 611 | tree nb_iters = number_of_latch_executions (loop); |
d37fc3aa | 612 | sese_l region = scop->scop_info->region; |
216cc294 | 613 | gcc_assert (loop_in_sese_p (loop, region)); |
2abae5f1 | 614 | |
33ad93b9 | 615 | isl_set *inner = isl_set_copy (outer); |
33ad93b9 | 616 | int pos = isl_set_dim (outer, isl_dim_set); |
b47595f7 | 617 | isl_val *v; |
33ad93b9 RG |
618 | mpz_t g; |
619 | ||
620 | mpz_init (g); | |
33ad93b9 RG |
621 | |
622 | inner = isl_set_add_dims (inner, isl_dim_set, 1); | |
8e4dc590 | 623 | isl_space *space = isl_set_get_space (inner); |
2abae5f1 SP |
624 | |
625 | /* 0 <= loop_i */ | |
8e4dc590 | 626 | isl_constraint *c = isl_inequality_alloc |
33ad93b9 RG |
627 | (isl_local_space_from_space (isl_space_copy (space))); |
628 | c = isl_constraint_set_coefficient_si (c, isl_dim_set, pos, 1); | |
629 | inner = isl_set_add_constraint (inner, c); | |
2abae5f1 | 630 | |
33ad93b9 | 631 | /* loop_i <= cst_nb_iters */ |
2abae5f1 SP |
632 | if (TREE_CODE (nb_iters) == INTEGER_CST) |
633 | { | |
33ad93b9 | 634 | c = isl_inequality_alloc |
c3284718 | 635 | (isl_local_space_from_space (isl_space_copy (space))); |
33ad93b9 RG |
636 | c = isl_constraint_set_coefficient_si (c, isl_dim_set, pos, -1); |
637 | tree_int_to_gmp (nb_iters, g); | |
8e4dc590 | 638 | v = isl_val_int_from_gmp (scop->isl_context, g); |
b47595f7 | 639 | c = isl_constraint_set_constant_val (c, v); |
33ad93b9 | 640 | inner = isl_set_add_constraint (inner, c); |
2abae5f1 | 641 | } |
33ad93b9 RG |
642 | |
643 | /* loop_i <= expr_nb_iters */ | |
2abae5f1 SP |
644 | else if (!chrec_contains_undetermined (nb_iters)) |
645 | { | |
33ad93b9 | 646 | isl_pw_aff *aff; |
2abae5f1 | 647 | |
2abae5f1 | 648 | nb_iters = scalar_evolution_in_region (region, loop, nb_iters); |
33ad93b9 | 649 | |
36f40be0 AK |
650 | /* Bail out as we do not know the scev. */ |
651 | if (chrec_contains_undetermined (nb_iters)) | |
652 | return cleanup_loop_iter_dom (inner, outer, space, g); | |
653 | ||
33ad93b9 | 654 | aff = extract_affine (scop, nb_iters, isl_set_get_space (inner)); |
8e4dc590 | 655 | isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff)); |
33ad93b9 RG |
656 | valid = isl_set_project_out (valid, isl_dim_set, 0, |
657 | isl_set_dim (valid, isl_dim_set)); | |
36f40be0 AK |
658 | |
659 | if (valid) | |
660 | scop->param_context = isl_set_intersect (scop->param_context, valid); | |
33ad93b9 | 661 | |
8e4dc590 AK |
662 | isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space)); |
663 | isl_aff *al = isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls), | |
664 | isl_dim_in, pos, 1); | |
665 | isl_set *le = isl_pw_aff_le_set (isl_pw_aff_from_aff (al), | |
666 | isl_pw_aff_copy (aff)); | |
33ad93b9 | 667 | inner = isl_set_intersect (inner, le); |
2abae5f1 | 668 | |
8e4dc590 | 669 | widest_int nit; |
652c4c71 | 670 | if (max_stmt_executions (loop, &nit)) |
33ad93b9 RG |
671 | { |
672 | /* Insert in the context the constraints from the | |
673 | estimation of the number of iterations NIT and the | |
674 | symbolic number of iterations (involving parameter | |
675 | names) NB_ITERS. First, build the affine expression | |
676 | "NIT - NB_ITERS" and then say that it is positive, | |
677 | i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */ | |
33ad93b9 | 678 | mpz_t g; |
33ad93b9 | 679 | mpz_init (g); |
807e902e | 680 | wi::to_mpz (nit, g, SIGNED); |
33ad93b9 | 681 | mpz_sub_ui (g, g, 1); |
8e4dc590 AK |
682 | |
683 | isl_pw_aff *approx | |
684 | = extract_affine_gmp (g, isl_set_get_space (inner)); | |
685 | isl_set *x = isl_pw_aff_ge_set (approx, aff); | |
33ad93b9 RG |
686 | x = isl_set_project_out (x, isl_dim_set, 0, |
687 | isl_set_dim (x, isl_dim_set)); | |
8e4dc590 | 688 | scop->param_context = isl_set_intersect (scop->param_context, x); |
33ad93b9 | 689 | |
8e4dc590 | 690 | isl_constraint *c = isl_inequality_alloc |
33ad93b9 RG |
691 | (isl_local_space_from_space (isl_space_copy (space))); |
692 | c = isl_constraint_set_coefficient_si (c, isl_dim_set, pos, -1); | |
8e4dc590 | 693 | v = isl_val_int_from_gmp (scop->isl_context, g); |
33ad93b9 | 694 | mpz_clear (g); |
b47595f7 | 695 | c = isl_constraint_set_constant_val (c, v); |
33ad93b9 RG |
696 | inner = isl_set_add_constraint (inner, c); |
697 | } | |
2b91f098 RB |
698 | else |
699 | isl_pw_aff_free (aff); | |
2abae5f1 SP |
700 | } |
701 | else | |
702 | gcc_unreachable (); | |
703 | ||
36f40be0 AK |
704 | if (loop->inner |
705 | && !build_loop_iteration_domains (scop, loop->inner, nb + 1, | |
706 | isl_set_copy (inner), doms)) | |
707 | return cleanup_loop_iter_dom (inner, outer, space, g); | |
2abae5f1 SP |
708 | |
709 | if (nb != 0 | |
710 | && loop->next | |
36f40be0 AK |
711 | && loop_in_sese_p (loop->next, region) |
712 | && !build_loop_iteration_domains (scop, loop->next, nb, | |
713 | isl_set_copy (outer), doms)) | |
714 | return cleanup_loop_iter_dom (inner, outer, space, g); | |
2abae5f1 | 715 | |
33ad93b9 | 716 | doms[loop->num] = inner; |
2abae5f1 | 717 | |
33ad93b9 RG |
718 | isl_set_free (outer); |
719 | isl_space_free (space); | |
33ad93b9 | 720 | mpz_clear (g); |
36f40be0 | 721 | return true; |
2abae5f1 SP |
722 | } |
723 | ||
724 | /* Returns a linear expression for tree T evaluated in PBB. */ | |
725 | ||
33ad93b9 RG |
726 | static isl_pw_aff * |
727 | create_pw_aff_from_tree (poly_bb_p pbb, tree t) | |
2abae5f1 | 728 | { |
33ad93b9 | 729 | scop_p scop = PBB_SCOP (pbb); |
2abae5f1 | 730 | |
d37fc3aa | 731 | t = scalar_evolution_in_region (scop->scop_info->region, pbb_loop (pbb), t); |
36f40be0 AK |
732 | |
733 | /* Bail out as we do not know the scev. */ | |
734 | if (chrec_contains_undetermined (t)) | |
735 | return NULL; | |
736 | ||
2abae5f1 SP |
737 | gcc_assert (!automatically_generated_chrec_p (t)); |
738 | ||
33ad93b9 | 739 | return extract_affine (scop, t, isl_set_get_space (pbb->domain)); |
2abae5f1 SP |
740 | } |
741 | ||
33ad93b9 RG |
742 | /* Add conditional statement STMT to pbb. CODE is used as the comparison |
743 | operator. This allows us to invert the condition or to handle | |
744 | inequalities. */ | |
2abae5f1 | 745 | |
36f40be0 | 746 | static bool |
538dd0b7 | 747 | add_condition_to_pbb (poly_bb_p pbb, gcond *stmt, enum tree_code code) |
2abae5f1 | 748 | { |
33ad93b9 | 749 | isl_pw_aff *lhs = create_pw_aff_from_tree (pbb, gimple_cond_lhs (stmt)); |
36f40be0 AK |
750 | if (!lhs) |
751 | return false; | |
752 | ||
33ad93b9 | 753 | isl_pw_aff *rhs = create_pw_aff_from_tree (pbb, gimple_cond_rhs (stmt)); |
36f40be0 AK |
754 | if (!rhs) |
755 | { | |
756 | isl_pw_aff_free (lhs); | |
757 | return false; | |
758 | } | |
2abae5f1 | 759 | |
36f40be0 | 760 | isl_set *cond; |
33ad93b9 | 761 | switch (code) |
2abae5f1 | 762 | { |
33ad93b9 RG |
763 | case LT_EXPR: |
764 | cond = isl_pw_aff_lt_set (lhs, rhs); | |
765 | break; | |
2abae5f1 | 766 | |
33ad93b9 RG |
767 | case GT_EXPR: |
768 | cond = isl_pw_aff_gt_set (lhs, rhs); | |
769 | break; | |
2abae5f1 | 770 | |
33ad93b9 RG |
771 | case LE_EXPR: |
772 | cond = isl_pw_aff_le_set (lhs, rhs); | |
773 | break; | |
2abae5f1 | 774 | |
33ad93b9 RG |
775 | case GE_EXPR: |
776 | cond = isl_pw_aff_ge_set (lhs, rhs); | |
777 | break; | |
2abae5f1 | 778 | |
33ad93b9 RG |
779 | case EQ_EXPR: |
780 | cond = isl_pw_aff_eq_set (lhs, rhs); | |
781 | break; | |
2abae5f1 | 782 | |
33ad93b9 RG |
783 | case NE_EXPR: |
784 | cond = isl_pw_aff_ne_set (lhs, rhs); | |
785 | break; | |
2abae5f1 | 786 | |
33ad93b9 | 787 | default: |
c3284718 RS |
788 | isl_pw_aff_free (lhs); |
789 | isl_pw_aff_free (rhs); | |
36f40be0 | 790 | return true; |
2abae5f1 | 791 | } |
33ad93b9 RG |
792 | |
793 | cond = isl_set_coalesce (cond); | |
794 | cond = isl_set_set_tuple_id (cond, isl_set_get_tuple_id (pbb->domain)); | |
795 | pbb->domain = isl_set_intersect (pbb->domain, cond); | |
36f40be0 | 796 | return true; |
2abae5f1 SP |
797 | } |
798 | ||
799 | /* Add conditions to the domain of PBB. */ | |
800 | ||
36f40be0 | 801 | static bool |
2abae5f1 SP |
802 | add_conditions_to_domain (poly_bb_p pbb) |
803 | { | |
804 | unsigned int i; | |
355fe088 | 805 | gimple *stmt; |
65ef70d6 | 806 | gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); |
2abae5f1 | 807 | |
9771b263 | 808 | if (GBB_CONDITIONS (gbb).is_empty ()) |
36f40be0 | 809 | return true; |
2abae5f1 | 810 | |
9771b263 | 811 | FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt) |
2abae5f1 SP |
812 | switch (gimple_code (stmt)) |
813 | { | |
814 | case GIMPLE_COND: | |
815 | { | |
4bc4dd11 AK |
816 | /* Don't constrain on anything else than INTEGER_TYPE. */ |
817 | if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt))) != INTEGER_TYPE) | |
818 | break; | |
819 | ||
538dd0b7 DM |
820 | gcond *cond_stmt = as_a <gcond *> (stmt); |
821 | enum tree_code code = gimple_cond_code (cond_stmt); | |
2abae5f1 SP |
822 | |
823 | /* The conditions for ELSE-branches are inverted. */ | |
9771b263 | 824 | if (!GBB_CONDITION_CASES (gbb)[i]) |
2abae5f1 SP |
825 | code = invert_tree_comparison (code, false); |
826 | ||
36f40be0 AK |
827 | if (!add_condition_to_pbb (pbb, cond_stmt, code)) |
828 | return false; | |
2abae5f1 SP |
829 | break; |
830 | } | |
831 | ||
832 | case GIMPLE_SWITCH: | |
33ad93b9 | 833 | /* Switch statements are not supported right now - fall through. */ |
2abae5f1 SP |
834 | |
835 | default: | |
836 | gcc_unreachable (); | |
837 | break; | |
838 | } | |
36f40be0 AK |
839 | |
840 | return true; | |
2abae5f1 SP |
841 | } |
842 | ||
efa21390 SP |
843 | /* Traverses all the GBBs of the SCOP and add their constraints to the |
844 | iteration domains. */ | |
845 | ||
36f40be0 | 846 | static bool |
efa21390 SP |
847 | add_conditions_to_constraints (scop_p scop) |
848 | { | |
849 | int i; | |
850 | poly_bb_p pbb; | |
851 | ||
b0b5710c | 852 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) |
36f40be0 AK |
853 | if (!add_conditions_to_domain (pbb)) |
854 | return false; | |
855 | ||
856 | return true; | |
efa21390 SP |
857 | } |
858 | ||
2abae5f1 SP |
859 | /* Add constraints on the possible values of parameter P from the type |
860 | of P. */ | |
861 | ||
862 | static void | |
33ad93b9 | 863 | add_param_constraints (scop_p scop, graphite_dim_t p) |
2abae5f1 | 864 | { |
65b016eb | 865 | tree parameter = scop->scop_info->params[p]; |
2abae5f1 | 866 | tree type = TREE_TYPE (parameter); |
3640d64c SP |
867 | tree lb = NULL_TREE; |
868 | tree ub = NULL_TREE; | |
2abae5f1 | 869 | |
697f511d SP |
870 | if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type)) |
871 | lb = lower_bound_in_type (type, type); | |
872 | else | |
873 | lb = TYPE_MIN_VALUE (type); | |
874 | ||
875 | if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type)) | |
876 | ub = upper_bound_in_type (type, type); | |
877 | else | |
878 | ub = TYPE_MAX_VALUE (type); | |
2abae5f1 SP |
879 | |
880 | if (lb) | |
881 | { | |
8e4dc590 | 882 | isl_space *space = isl_set_get_space (scop->param_context); |
33ad93b9 RG |
883 | isl_constraint *c; |
884 | mpz_t g; | |
b47595f7 | 885 | isl_val *v; |
33ad93b9 RG |
886 | |
887 | c = isl_inequality_alloc (isl_local_space_from_space (space)); | |
888 | mpz_init (g); | |
33ad93b9 | 889 | tree_int_to_gmp (lb, g); |
8e4dc590 | 890 | v = isl_val_int_from_gmp (scop->isl_context, g); |
b47595f7 | 891 | v = isl_val_neg (v); |
33ad93b9 | 892 | mpz_clear (g); |
b47595f7 | 893 | c = isl_constraint_set_constant_val (c, v); |
33ad93b9 RG |
894 | c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, 1); |
895 | ||
8e4dc590 | 896 | scop->param_context = isl_set_add_constraint (scop->param_context, c); |
2abae5f1 SP |
897 | } |
898 | ||
899 | if (ub) | |
900 | { | |
8e4dc590 | 901 | isl_space *space = isl_set_get_space (scop->param_context); |
33ad93b9 RG |
902 | isl_constraint *c; |
903 | mpz_t g; | |
b47595f7 | 904 | isl_val *v; |
33ad93b9 RG |
905 | |
906 | c = isl_inequality_alloc (isl_local_space_from_space (space)); | |
907 | ||
908 | mpz_init (g); | |
33ad93b9 | 909 | tree_int_to_gmp (ub, g); |
8e4dc590 | 910 | v = isl_val_int_from_gmp (scop->isl_context, g); |
33ad93b9 | 911 | mpz_clear (g); |
b47595f7 | 912 | c = isl_constraint_set_constant_val (c, v); |
33ad93b9 RG |
913 | c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, -1); |
914 | ||
8e4dc590 | 915 | scop->param_context = isl_set_add_constraint (scop->param_context, c); |
2abae5f1 SP |
916 | } |
917 | } | |
918 | ||
919 | /* Build the context of the SCOP. The context usually contains extra | |
920 | constraints that are added to the iteration domains that constrain | |
921 | some parameters. */ | |
922 | ||
923 | static void | |
924 | build_scop_context (scop_p scop) | |
925 | { | |
2abae5f1 SP |
926 | graphite_dim_t p, n = scop_nb_params (scop); |
927 | ||
2abae5f1 | 928 | for (p = 0; p < n; p++) |
33ad93b9 | 929 | add_param_constraints (scop, p); |
2abae5f1 SP |
930 | } |
931 | ||
932 | /* Build the iteration domains: the loops belonging to the current | |
933 | SCOP, and that vary for the execution of the current basic block. | |
934 | Returns false if there is no loop in SCOP. */ | |
935 | ||
36f40be0 | 936 | static bool |
2abae5f1 SP |
937 | build_scop_iteration_domain (scop_p scop) |
938 | { | |
d37fc3aa | 939 | sese_info_p region = scop->scop_info; |
0fc822d0 | 940 | int nb_loops = number_of_loops (cfun); |
33ad93b9 | 941 | isl_set **doms = XCNEWVEC (isl_set *, nb_loops); |
36f40be0 | 942 | bool res = true; |
8e4dc590 AK |
943 | int i; |
944 | struct loop *loop; | |
65b016eb | 945 | FOR_EACH_VEC_ELT (region->loop_nest, i, loop) |
36f40be0 AK |
946 | if (!loop_in_sese_p (loop_outer (loop), region->region) |
947 | && !build_loop_iteration_domains (scop, loop, 0, | |
948 | isl_set_copy (scop->param_context), doms)) | |
949 | { | |
950 | res = false; | |
951 | goto cleanup; | |
952 | } | |
2abae5f1 | 953 | |
8e4dc590 | 954 | poly_bb_p pbb; |
b0b5710c | 955 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) |
33ad93b9 RG |
956 | { |
957 | loop = pbb_loop (pbb); | |
958 | ||
959 | if (doms[loop->num]) | |
960 | pbb->domain = isl_set_copy (doms[loop->num]); | |
961 | else | |
8e4dc590 | 962 | pbb->domain = isl_set_copy (scop->param_context); |
33ad93b9 RG |
963 | |
964 | pbb->domain = isl_set_set_tuple_id (pbb->domain, | |
965 | isl_id_for_pbb (scop, pbb)); | |
966 | } | |
2abae5f1 | 967 | |
36f40be0 | 968 | cleanup: |
8e4dc590 | 969 | for (int i = 0; i < nb_loops; i++) |
33ad93b9 RG |
970 | if (doms[i]) |
971 | isl_set_free (doms[i]); | |
2abae5f1 | 972 | |
33ad93b9 | 973 | free (doms); |
36f40be0 | 974 | return res; |
2abae5f1 SP |
975 | } |
976 | ||
977 | /* Add a constrain to the ACCESSES polyhedron for the alias set of | |
978 | data reference DR. ACCESSP_NB_DIMS is the dimension of the | |
979 | ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration | |
980 | domain. */ | |
981 | ||
33ad93b9 | 982 | static isl_map * |
09fefdad | 983 | pdr_add_alias_set (isl_map *acc, dr_info &dri) |
2abae5f1 | 984 | { |
790befae | 985 | isl_constraint *c = isl_equality_alloc |
33ad93b9 | 986 | (isl_local_space_from_space (isl_map_get_space (acc))); |
65b016eb | 987 | /* Positive numbers for all alias sets. */ |
09fefdad | 988 | c = isl_constraint_set_constant_si (c, -dri.alias_set); |
33ad93b9 RG |
989 | c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1); |
990 | ||
991 | return isl_map_add_constraint (acc, c); | |
992 | } | |
993 | ||
65b016eb AK |
994 | /* Add a constrain to the ACCESSES polyhedron for the alias set of |
995 | data reference DR. ACCESSP_NB_DIMS is the dimension of the | |
996 | ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration | |
997 | domain. */ | |
998 | ||
999 | static isl_map * | |
1000 | add_scalar_version_numbers (isl_map *acc, tree var) | |
1001 | { | |
1002 | isl_constraint *c = isl_equality_alloc | |
1003 | (isl_local_space_from_space (isl_map_get_space (acc))); | |
1004 | int max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP); | |
1005 | /* Each scalar variables has a unique alias set number starting from | |
1006 | max_arrays. */ | |
1007 | c = isl_constraint_set_constant_si (c, -max_arrays - SSA_NAME_VERSION (var)); | |
1008 | c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1); | |
1009 | ||
1010 | return isl_map_add_constraint (acc, c); | |
1011 | } | |
1012 | ||
33ad93b9 RG |
1013 | /* Assign the affine expression INDEX to the output dimension POS of |
1014 | MAP and return the result. */ | |
1015 | ||
1016 | static isl_map * | |
1017 | set_index (isl_map *map, int pos, isl_pw_aff *index) | |
1018 | { | |
1019 | isl_map *index_map; | |
1020 | int len = isl_map_dim (map, isl_dim_out); | |
1021 | isl_id *id; | |
1022 | ||
1023 | index_map = isl_map_from_pw_aff (index); | |
1024 | index_map = isl_map_insert_dims (index_map, isl_dim_out, 0, pos); | |
1025 | index_map = isl_map_add_dims (index_map, isl_dim_out, len - pos - 1); | |
2abae5f1 | 1026 | |
33ad93b9 RG |
1027 | id = isl_map_get_tuple_id (map, isl_dim_out); |
1028 | index_map = isl_map_set_tuple_id (index_map, isl_dim_out, id); | |
1029 | id = isl_map_get_tuple_id (map, isl_dim_in); | |
1030 | index_map = isl_map_set_tuple_id (index_map, isl_dim_in, id); | |
2abae5f1 | 1031 | |
33ad93b9 | 1032 | return isl_map_intersect (map, index_map); |
2abae5f1 SP |
1033 | } |
1034 | ||
1035 | /* Add to ACCESSES polyhedron equalities defining the access functions | |
1036 | to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES | |
1037 | polyhedron, DOM_NB_DIMS is the dimension of the iteration domain. | |
1038 | PBB is the poly_bb_p that contains the data reference DR. */ | |
1039 | ||
33ad93b9 | 1040 | static isl_map * |
09fefdad | 1041 | pdr_add_memory_accesses (isl_map *acc, dr_info &dri) |
2abae5f1 | 1042 | { |
09fefdad AK |
1043 | data_reference_p dr = dri.dr; |
1044 | poly_bb_p pbb = dri.pbb; | |
2abae5f1 | 1045 | int i, nb_subscripts = DR_NUM_DIMENSIONS (dr); |
2abae5f1 | 1046 | scop_p scop = PBB_SCOP (pbb); |
2abae5f1 SP |
1047 | |
1048 | for (i = 0; i < nb_subscripts; i++) | |
1049 | { | |
33ad93b9 | 1050 | isl_pw_aff *aff; |
2abae5f1 SP |
1051 | tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i); |
1052 | ||
33ad93b9 RG |
1053 | aff = extract_affine (scop, afn, |
1054 | isl_space_domain (isl_map_get_space (acc))); | |
1055 | acc = set_index (acc, i + 1, aff); | |
2abae5f1 SP |
1056 | } |
1057 | ||
33ad93b9 | 1058 | return acc; |
2abae5f1 SP |
1059 | } |
1060 | ||
1061 | /* Add constrains representing the size of the accessed data to the | |
66096911 SP |
1062 | ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the |
1063 | ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration | |
2abae5f1 SP |
1064 | domain. */ |
1065 | ||
33ad93b9 | 1066 | static isl_set * |
24757752 AK |
1067 | pdr_add_data_dimensions (isl_set *subscript_sizes, scop_p scop, |
1068 | data_reference_p dr) | |
2abae5f1 SP |
1069 | { |
1070 | tree ref = DR_REF (dr); | |
2abae5f1 | 1071 | |
24757752 AK |
1072 | int nb_subscripts = DR_NUM_DIMENSIONS (dr); |
1073 | for (int i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0)) | |
2abae5f1 | 1074 | { |
98f3eb1f | 1075 | if (TREE_CODE (ref) != ARRAY_REF) |
24757752 | 1076 | return subscript_sizes; |
2abae5f1 | 1077 | |
24757752 AK |
1078 | tree low = array_ref_low_bound (ref); |
1079 | tree high = array_ref_up_bound (ref); | |
98f3eb1f | 1080 | |
33ad93b9 RG |
1081 | /* XXX The PPL code dealt separately with |
1082 | subscript - low >= 0 and high - subscript >= 0 in case one of | |
1083 | the two bounds isn't known. Do the same here? */ | |
1084 | ||
9541ffee | 1085 | if (tree_fits_shwi_p (low) |
33ad93b9 | 1086 | && high |
9541ffee | 1087 | && tree_fits_shwi_p (high) |
3899a0b2 SP |
1088 | /* 1-element arrays at end of structures may extend over |
1089 | their declared size. */ | |
1090 | && !(array_at_struct_end_p (ref) | |
1091 | && operand_equal_p (low, high, 0))) | |
98f3eb1f | 1092 | { |
33ad93b9 RG |
1093 | isl_id *id; |
1094 | isl_aff *aff; | |
1095 | isl_set *univ, *lbs, *ubs; | |
1096 | isl_pw_aff *index; | |
33ad93b9 | 1097 | isl_set *valid; |
24757752 AK |
1098 | isl_space *space = isl_set_get_space (subscript_sizes); |
1099 | isl_pw_aff *lb = extract_affine_int (low, isl_space_copy (space)); | |
1100 | isl_pw_aff *ub = extract_affine_int (high, isl_space_copy (space)); | |
33ad93b9 RG |
1101 | |
1102 | /* high >= 0 */ | |
1103 | valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub)); | |
1104 | valid = isl_set_project_out (valid, isl_dim_set, 0, | |
1105 | isl_set_dim (valid, isl_dim_set)); | |
8e4dc590 | 1106 | scop->param_context = isl_set_intersect (scop->param_context, valid); |
33ad93b9 | 1107 | |
33ad93b9 RG |
1108 | aff = isl_aff_zero_on_domain (isl_local_space_from_space (space)); |
1109 | aff = isl_aff_add_coefficient_si (aff, isl_dim_in, i + 1, 1); | |
1110 | univ = isl_set_universe (isl_space_domain (isl_aff_get_space (aff))); | |
1111 | index = isl_pw_aff_alloc (univ, aff); | |
1112 | ||
24757752 | 1113 | id = isl_set_get_tuple_id (subscript_sizes); |
33ad93b9 RG |
1114 | lb = isl_pw_aff_set_tuple_id (lb, isl_dim_in, isl_id_copy (id)); |
1115 | ub = isl_pw_aff_set_tuple_id (ub, isl_dim_in, id); | |
1116 | ||
1117 | /* low <= sub_i <= high */ | |
1118 | lbs = isl_pw_aff_ge_set (isl_pw_aff_copy (index), lb); | |
1119 | ubs = isl_pw_aff_le_set (index, ub); | |
24757752 AK |
1120 | subscript_sizes = isl_set_intersect (subscript_sizes, lbs); |
1121 | subscript_sizes = isl_set_intersect (subscript_sizes, ubs); | |
98f3eb1f | 1122 | } |
2abae5f1 | 1123 | } |
33ad93b9 | 1124 | |
24757752 | 1125 | return subscript_sizes; |
2abae5f1 SP |
1126 | } |
1127 | ||
65b016eb | 1128 | /* Build data accesses for DRI. */ |
2abae5f1 SP |
1129 | |
1130 | static void | |
09fefdad | 1131 | build_poly_dr (dr_info &dri) |
2abae5f1 | 1132 | { |
33ad93b9 | 1133 | isl_map *acc; |
24757752 | 1134 | isl_set *subscript_sizes; |
09fefdad AK |
1135 | poly_bb_p pbb = dri.pbb; |
1136 | data_reference_p dr = dri.dr; | |
33ad93b9 | 1137 | scop_p scop = PBB_SCOP (pbb); |
65b016eb | 1138 | isl_id *id = isl_id_for_dr (scop); |
2abae5f1 | 1139 | |
33ad93b9 RG |
1140 | { |
1141 | isl_space *dc = isl_set_get_space (pbb->domain); | |
1142 | int nb_out = 1 + DR_NUM_DIMENSIONS (dr); | |
1143 | isl_space *space = isl_space_add_dims (isl_space_from_domain (dc), | |
1144 | isl_dim_out, nb_out); | |
2abae5f1 | 1145 | |
33ad93b9 | 1146 | acc = isl_map_universe (space); |
65b016eb | 1147 | acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_copy (id)); |
33ad93b9 | 1148 | } |
2abae5f1 | 1149 | |
09fefdad AK |
1150 | acc = pdr_add_alias_set (acc, dri); |
1151 | acc = pdr_add_memory_accesses (acc, dri); | |
2abae5f1 | 1152 | |
33ad93b9 | 1153 | { |
33ad93b9 | 1154 | int nb = 1 + DR_NUM_DIMENSIONS (dr); |
8e4dc590 | 1155 | isl_space *space = isl_space_set_alloc (scop->isl_context, 0, nb); |
33ad93b9 RG |
1156 | |
1157 | space = isl_space_set_tuple_id (space, isl_dim_set, id); | |
24757752 AK |
1158 | subscript_sizes = isl_set_nat_universe (space); |
1159 | subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0, | |
09fefdad | 1160 | dri.alias_set); |
24757752 | 1161 | subscript_sizes = pdr_add_data_dimensions (subscript_sizes, scop, dr); |
33ad93b9 | 1162 | } |
2abae5f1 | 1163 | |
65b016eb AK |
1164 | new_poly_dr (pbb, DR_STMT (dr), DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, |
1165 | acc, subscript_sizes); | |
2abae5f1 SP |
1166 | } |
1167 | ||
278b1a1d | 1168 | static void |
65b016eb AK |
1169 | build_poly_sr_1 (poly_bb_p pbb, gimple *stmt, tree var, enum poly_dr_type kind, |
1170 | isl_map *acc, isl_set *subscript_sizes) | |
278b1a1d | 1171 | { |
65b016eb AK |
1172 | int max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP); |
1173 | /* Each scalar variables has a unique alias set number starting from | |
1174 | max_arrays. */ | |
1175 | subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0, | |
1176 | max_arrays + SSA_NAME_VERSION (var)); | |
1177 | ||
1178 | new_poly_dr (pbb, stmt, kind, add_scalar_version_numbers (acc, var), | |
1179 | subscript_sizes); | |
278b1a1d SP |
1180 | } |
1181 | ||
65b016eb | 1182 | /* Record all cross basic block scalar variables in PBB. */ |
2abae5f1 SP |
1183 | |
1184 | static void | |
65b016eb | 1185 | build_poly_sr (poly_bb_p pbb) |
2abae5f1 | 1186 | { |
65b016eb | 1187 | scop_p scop = PBB_SCOP (pbb); |
65ef70d6 | 1188 | gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); |
65b016eb AK |
1189 | vec<scalar_use> reads = gbb->read_scalar_refs; |
1190 | vec<tree> writes = gbb->write_scalar_refs; | |
1c2a7491 | 1191 | |
65b016eb AK |
1192 | isl_space *dc = isl_set_get_space (pbb->domain); |
1193 | int nb_out = 1; | |
1194 | isl_space *space = isl_space_add_dims (isl_space_from_domain (dc), | |
1195 | isl_dim_out, nb_out); | |
1196 | isl_id *id = isl_id_for_dr (scop); | |
1197 | space = isl_space_set_tuple_id (space, isl_dim_set, isl_id_copy (id)); | |
1198 | isl_map *acc = isl_map_universe (isl_space_copy (space)); | |
1199 | acc = isl_map_set_tuple_id (acc, isl_dim_out, id); | |
1200 | isl_set *subscript_sizes = isl_set_nat_universe (space); | |
9773d730 | 1201 | |
caf5b4df | 1202 | int i; |
65b016eb AK |
1203 | tree var; |
1204 | FOR_EACH_VEC_ELT (writes, i, var) | |
1205 | build_poly_sr_1 (pbb, SSA_NAME_DEF_STMT (var), var, PDR_WRITE, | |
1206 | isl_map_copy (acc), isl_set_copy (subscript_sizes)); | |
5d737345 | 1207 | |
65b016eb AK |
1208 | scalar_use *use; |
1209 | FOR_EACH_VEC_ELT (reads, i, use) | |
1210 | build_poly_sr_1 (pbb, use->first, use->second, PDR_READ, isl_map_copy (acc), | |
1211 | isl_set_copy (subscript_sizes)); | |
d5b5a232 | 1212 | |
65b016eb AK |
1213 | isl_map_free (acc); |
1214 | isl_set_free (subscript_sizes); | |
5dcc64d9 SP |
1215 | } |
1216 | ||
65b016eb | 1217 | /* Build data references in SCOP. */ |
ee646fc6 | 1218 | |
efa21390 | 1219 | static void |
65b016eb | 1220 | build_scop_drs (scop_p scop) |
ee646fc6 | 1221 | { |
caf5b4df | 1222 | int i; |
65b016eb AK |
1223 | dr_info *dri; |
1224 | FOR_EACH_VEC_ELT (scop->drs, i, dri) | |
1225 | build_poly_dr (*dri); | |
5dcc64d9 | 1226 | |
65b016eb AK |
1227 | poly_bb_p pbb; |
1228 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) | |
1229 | build_poly_sr (pbb); | |
2abae5f1 SP |
1230 | } |
1231 | ||
2abae5f1 SP |
1232 | /* Builds the polyhedral representation for a SESE region. */ |
1233 | ||
36f40be0 | 1234 | bool |
2abae5f1 SP |
1235 | build_poly_scop (scop_p scop) |
1236 | { | |
076d564d | 1237 | set_scop_parameter_dim (scop); |
36f40be0 AK |
1238 | if (!build_scop_iteration_domain (scop)) |
1239 | return false; | |
1240 | ||
2abae5f1 | 1241 | build_scop_context (scop); |
36f40be0 AK |
1242 | |
1243 | if (!add_conditions_to_constraints (scop)) | |
1244 | return false; | |
efa21390 | 1245 | |
efa21390 | 1246 | build_scop_drs (scop); |
504fbc11 | 1247 | build_scop_minimal_scattering (scop); |
0473915e | 1248 | build_scop_original_schedule (scop); |
36f40be0 | 1249 | return true; |
2abae5f1 | 1250 | } |
9c358739 | 1251 | #endif /* HAVE_isl */ |