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