]>
Commit | Line | Data |
---|---|---|
2abae5f1 | 1 | /* Conversion of SESE regions to Polyhedra. |
cbe34bb5 | 2 | Copyright (C) 2009-2017 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 | |
cf98f0f4 | 59 | #include "graphite.h" |
2abae5f1 | 60 | |
33ad93b9 RG |
61 | /* Assigns to RES the value of the INTEGER_CST T. */ |
62 | ||
63 | static inline void | |
64 | tree_int_to_gmp (tree t, mpz_t res) | |
65 | { | |
807e902e | 66 | wi::to_mpz (t, res, TYPE_SIGN (TREE_TYPE (t))); |
33ad93b9 RG |
67 | } |
68 | ||
e357a5e0 | 69 | /* Return an isl identifier for the polyhedral basic block PBB. */ |
33ad93b9 RG |
70 | |
71 | static isl_id * | |
72 | isl_id_for_pbb (scop_p s, poly_bb_p pbb) | |
73 | { | |
efcc8d38 | 74 | char name[14]; |
33ad93b9 | 75 | snprintf (name, sizeof (name), "S_%d", pbb_index (pbb)); |
8e4dc590 | 76 | return isl_id_alloc (s->isl_context, name, pbb); |
33ad93b9 RG |
77 | } |
78 | ||
33ad93b9 RG |
79 | static isl_pw_aff *extract_affine (scop_p, tree, __isl_take isl_space *space); |
80 | ||
81 | /* Extract an affine expression from the chain of recurrence E. */ | |
2abae5f1 | 82 | |
33ad93b9 RG |
83 | static isl_pw_aff * |
84 | extract_affine_chrec (scop_p s, tree e, __isl_take isl_space *space) | |
85 | { | |
86 | isl_pw_aff *lhs = extract_affine (s, CHREC_LEFT (e), isl_space_copy (space)); | |
87 | isl_pw_aff *rhs = extract_affine (s, CHREC_RIGHT (e), isl_space_copy (space)); | |
88 | isl_local_space *ls = isl_local_space_from_space (space); | |
d37fc3aa | 89 | unsigned pos = sese_loop_depth (s->scop_info->region, get_chrec_loop (e)) - 1; |
33ad93b9 RG |
90 | isl_aff *loop = isl_aff_set_coefficient_si |
91 | (isl_aff_zero_on_domain (ls), isl_dim_in, pos, 1); | |
92 | isl_pw_aff *l = isl_pw_aff_from_aff (loop); | |
93 | ||
94 | /* Before multiplying, make sure that the result is affine. */ | |
95 | gcc_assert (isl_pw_aff_is_cst (rhs) | |
96 | || isl_pw_aff_is_cst (l)); | |
97 | ||
98 | return isl_pw_aff_add (lhs, isl_pw_aff_mul (rhs, l)); | |
99 | } | |
100 | ||
101 | /* Extract an affine expression from the mult_expr E. */ | |
102 | ||
103 | static isl_pw_aff * | |
104 | extract_affine_mul (scop_p s, tree e, __isl_take isl_space *space) | |
105 | { | |
106 | isl_pw_aff *lhs = extract_affine (s, TREE_OPERAND (e, 0), | |
107 | isl_space_copy (space)); | |
108 | isl_pw_aff *rhs = extract_affine (s, TREE_OPERAND (e, 1), space); | |
2abae5f1 | 109 | |
33ad93b9 RG |
110 | if (!isl_pw_aff_is_cst (lhs) |
111 | && !isl_pw_aff_is_cst (rhs)) | |
112 | { | |
113 | isl_pw_aff_free (lhs); | |
114 | isl_pw_aff_free (rhs); | |
115 | return NULL; | |
2abae5f1 SP |
116 | } |
117 | ||
33ad93b9 | 118 | return isl_pw_aff_mul (lhs, rhs); |
2abae5f1 SP |
119 | } |
120 | ||
e357a5e0 | 121 | /* Return an isl identifier from the name of the ssa_name E. */ |
2abae5f1 | 122 | |
33ad93b9 RG |
123 | static isl_id * |
124 | isl_id_for_ssa_name (scop_p s, tree e) | |
2abae5f1 | 125 | { |
efcc8d38 | 126 | char name1[14]; |
49385686 AK |
127 | snprintf (name1, sizeof (name1), "P_%d", SSA_NAME_VERSION (e)); |
128 | return isl_id_alloc (s->isl_context, name1, e); | |
33ad93b9 | 129 | } |
2abae5f1 | 130 | |
e357a5e0 | 131 | /* Return an isl identifier for the data reference DR. Data references and |
65b016eb AK |
132 | scalar references get the same isl_id. They need to be comparable and are |
133 | distinguished through the first dimension, which contains the alias set or | |
134 | SSA_NAME_VERSION number. */ | |
2abae5f1 | 135 | |
33ad93b9 | 136 | static isl_id * |
65b016eb | 137 | isl_id_for_dr (scop_p s) |
33ad93b9 | 138 | { |
8e4dc590 | 139 | return isl_id_alloc (s->isl_context, "", 0); |
2abae5f1 SP |
140 | } |
141 | ||
33ad93b9 | 142 | /* Extract an affine expression from the ssa_name E. */ |
2abae5f1 | 143 | |
33ad93b9 RG |
144 | static isl_pw_aff * |
145 | extract_affine_name (scop_p s, tree e, __isl_take isl_space *space) | |
2abae5f1 | 146 | { |
8e4dc590 AK |
147 | isl_id *id = isl_id_for_ssa_name (s, e); |
148 | int dimension = isl_space_find_dim_by_id (space, isl_dim_param, id); | |
c3284718 | 149 | isl_id_free (id); |
8e4dc590 AK |
150 | isl_set *dom = isl_set_universe (isl_space_copy (space)); |
151 | isl_aff *aff = isl_aff_zero_on_domain (isl_local_space_from_space (space)); | |
33ad93b9 RG |
152 | aff = isl_aff_add_coefficient_si (aff, isl_dim_param, dimension, 1); |
153 | return isl_pw_aff_alloc (dom, aff); | |
154 | } | |
2abae5f1 | 155 | |
cc46a51d RB |
156 | /* Convert WI to a isl_val with CTX. */ |
157 | ||
158 | static __isl_give isl_val * | |
159 | isl_val_int_from_wi (isl_ctx *ctx, const widest_int &wi) | |
160 | { | |
161 | if (wi::neg_p (wi, SIGNED)) | |
162 | { | |
163 | widest_int mwi = -wi; | |
164 | return isl_val_neg (isl_val_int_from_chunks (ctx, mwi.get_len (), | |
165 | sizeof (HOST_WIDE_INT), | |
166 | mwi.get_val ())); | |
167 | } | |
168 | return isl_val_int_from_chunks (ctx, wi.get_len (), sizeof (HOST_WIDE_INT), | |
169 | wi.get_val ()); | |
170 | } | |
171 | ||
33ad93b9 | 172 | /* Extract an affine expression from the gmp constant G. */ |
2abae5f1 | 173 | |
33ad93b9 | 174 | static isl_pw_aff * |
cc46a51d | 175 | extract_affine_wi (const widest_int &g, __isl_take isl_space *space) |
33ad93b9 RG |
176 | { |
177 | isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space)); | |
178 | isl_aff *aff = isl_aff_zero_on_domain (ls); | |
179 | isl_set *dom = isl_set_universe (space); | |
8e4dc590 | 180 | isl_ctx *ct = isl_aff_get_ctx (aff); |
cc46a51d | 181 | isl_val *v = isl_val_int_from_wi (ct, g); |
b47595f7 | 182 | aff = isl_aff_add_constant_val (aff, v); |
2abae5f1 | 183 | |
33ad93b9 | 184 | return isl_pw_aff_alloc (dom, aff); |
2abae5f1 SP |
185 | } |
186 | ||
33ad93b9 | 187 | /* Extract an affine expression from the integer_cst E. */ |
2abae5f1 | 188 | |
33ad93b9 RG |
189 | static isl_pw_aff * |
190 | extract_affine_int (tree e, __isl_take isl_space *space) | |
191 | { | |
cc46a51d | 192 | isl_pw_aff *res = extract_affine_wi (wi::to_widest (e), space); |
33ad93b9 RG |
193 | return res; |
194 | } | |
195 | ||
196 | /* Compute pwaff mod 2^width. */ | |
197 | ||
198 | static isl_pw_aff * | |
199 | wrap (isl_pw_aff *pwaff, unsigned width) | |
2abae5f1 | 200 | { |
b47595f7 | 201 | isl_val *mod; |
2abae5f1 | 202 | |
24757752 | 203 | mod = isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff), width); |
b47595f7 MN |
204 | mod = isl_val_2exp (mod); |
205 | pwaff = isl_pw_aff_mod_val (pwaff, mod); | |
33ad93b9 RG |
206 | |
207 | return pwaff; | |
2abae5f1 SP |
208 | } |
209 | ||
2abae5f1 SP |
210 | /* When parameter NAME is in REGION, returns its index in SESE_PARAMS. |
211 | Otherwise returns -1. */ | |
212 | ||
213 | static inline int | |
bafcb153 | 214 | parameter_index_in_region_1 (tree name, sese_info_p region) |
2abae5f1 SP |
215 | { |
216 | int i; | |
217 | tree p; | |
218 | ||
219 | gcc_assert (TREE_CODE (name) == SSA_NAME); | |
220 | ||
65b016eb | 221 | FOR_EACH_VEC_ELT (region->params, i, p) |
2abae5f1 SP |
222 | if (p == name) |
223 | return i; | |
224 | ||
225 | return -1; | |
226 | } | |
227 | ||
33ad93b9 | 228 | /* Extract an affine expression from the tree E in the scop S. */ |
2abae5f1 | 229 | |
33ad93b9 RG |
230 | static isl_pw_aff * |
231 | extract_affine (scop_p s, tree e, __isl_take isl_space *space) | |
2abae5f1 | 232 | { |
33ad93b9 | 233 | isl_pw_aff *lhs, *rhs, *res; |
33ad93b9 RG |
234 | |
235 | if (e == chrec_dont_know) { | |
236 | isl_space_free (space); | |
237 | return NULL; | |
238 | } | |
2abae5f1 | 239 | |
f6b5c26b | 240 | tree type = TREE_TYPE (e); |
2abae5f1 SP |
241 | switch (TREE_CODE (e)) |
242 | { | |
243 | case POLYNOMIAL_CHREC: | |
33ad93b9 | 244 | res = extract_affine_chrec (s, e, space); |
2abae5f1 SP |
245 | break; |
246 | ||
247 | case MULT_EXPR: | |
33ad93b9 | 248 | res = extract_affine_mul (s, e, space); |
2abae5f1 SP |
249 | break; |
250 | ||
2abae5f1 | 251 | case POINTER_PLUS_EXPR: |
f6b5c26b RB |
252 | { |
253 | lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); | |
254 | /* The RHS of a pointer-plus expression is to be interpreted | |
255 | as signed value. Try to look through a sign-changing conversion | |
256 | first. */ | |
257 | tree tem = TREE_OPERAND (e, 1); | |
258 | STRIP_NOPS (tem); | |
259 | rhs = extract_affine (s, tem, space); | |
260 | if (TYPE_UNSIGNED (TREE_TYPE (tem))) | |
261 | rhs = wrap (rhs, TYPE_PRECISION (type) - 1); | |
262 | res = isl_pw_aff_add (lhs, rhs); | |
263 | break; | |
264 | } | |
265 | ||
266 | case PLUS_EXPR: | |
33ad93b9 RG |
267 | lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); |
268 | rhs = extract_affine (s, TREE_OPERAND (e, 1), space); | |
269 | res = isl_pw_aff_add (lhs, rhs); | |
2abae5f1 SP |
270 | break; |
271 | ||
272 | case MINUS_EXPR: | |
33ad93b9 RG |
273 | lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); |
274 | rhs = extract_affine (s, TREE_OPERAND (e, 1), space); | |
275 | res = isl_pw_aff_sub (lhs, rhs); | |
276 | break; | |
2abae5f1 | 277 | |
33ad93b9 | 278 | case BIT_NOT_EXPR: |
f6b5c26b RB |
279 | lhs = extract_affine (s, integer_minus_one_node, isl_space_copy (space)); |
280 | rhs = extract_affine (s, TREE_OPERAND (e, 0), space); | |
281 | res = isl_pw_aff_sub (lhs, rhs); | |
282 | break; | |
283 | ||
284 | case NEGATE_EXPR: | |
33ad93b9 RG |
285 | lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); |
286 | rhs = extract_affine (s, integer_minus_one_node, space); | |
287 | res = isl_pw_aff_mul (lhs, rhs); | |
288 | break; | |
2abae5f1 | 289 | |
33ad93b9 | 290 | case SSA_NAME: |
d37fc3aa | 291 | gcc_assert (-1 != parameter_index_in_region_1 (e, s->scop_info) |
8eedca0d | 292 | || defined_in_sese_p (e, s->scop_info->region)); |
33ad93b9 RG |
293 | res = extract_affine_name (s, e, space); |
294 | break; | |
2abae5f1 | 295 | |
33ad93b9 RG |
296 | case INTEGER_CST: |
297 | res = extract_affine_int (e, space); | |
298 | /* No need to wrap a single integer. */ | |
299 | return res; | |
2abae5f1 | 300 | |
33ad93b9 | 301 | CASE_CONVERT: |
f6b5c26b RB |
302 | res = extract_affine (s, TREE_OPERAND (e, 0), space); |
303 | /* signed values, even if overflow is undefined, get modulo-reduced. */ | |
304 | if (! TYPE_UNSIGNED (type)) | |
305 | res = wrap (res, TYPE_PRECISION (type) - 1); | |
306 | break; | |
307 | ||
33ad93b9 RG |
308 | case NON_LVALUE_EXPR: |
309 | res = extract_affine (s, TREE_OPERAND (e, 0), space); | |
310 | break; | |
2abae5f1 | 311 | |
33ad93b9 RG |
312 | default: |
313 | gcc_unreachable (); | |
314 | break; | |
315 | } | |
2abae5f1 | 316 | |
33ad93b9 RG |
317 | if (TYPE_UNSIGNED (type)) |
318 | res = wrap (res, TYPE_PRECISION (type)); | |
2abae5f1 | 319 | |
33ad93b9 RG |
320 | return res; |
321 | } | |
2abae5f1 | 322 | |
2abae5f1 SP |
323 | /* Returns a linear expression for tree T evaluated in PBB. */ |
324 | ||
33ad93b9 | 325 | static isl_pw_aff * |
8eedca0d | 326 | create_pw_aff_from_tree (poly_bb_p pbb, loop_p loop, tree t) |
2abae5f1 | 327 | { |
33ad93b9 | 328 | scop_p scop = PBB_SCOP (pbb); |
2abae5f1 | 329 | |
8eedca0d | 330 | t = scalar_evolution_in_region (scop->scop_info->region, loop, t); |
36f40be0 | 331 | |
adba512d | 332 | gcc_assert (!chrec_contains_undetermined (t)); |
2abae5f1 SP |
333 | gcc_assert (!automatically_generated_chrec_p (t)); |
334 | ||
33ad93b9 | 335 | return extract_affine (scop, t, isl_set_get_space (pbb->domain)); |
2abae5f1 SP |
336 | } |
337 | ||
33ad93b9 RG |
338 | /* Add conditional statement STMT to pbb. CODE is used as the comparison |
339 | operator. This allows us to invert the condition or to handle | |
340 | inequalities. */ | |
2abae5f1 | 341 | |
adba512d | 342 | static void |
538dd0b7 | 343 | add_condition_to_pbb (poly_bb_p pbb, gcond *stmt, enum tree_code code) |
2abae5f1 | 344 | { |
8eedca0d RB |
345 | loop_p loop = gimple_bb (stmt)->loop_father; |
346 | isl_pw_aff *lhs = create_pw_aff_from_tree (pbb, loop, gimple_cond_lhs (stmt)); | |
347 | isl_pw_aff *rhs = create_pw_aff_from_tree (pbb, loop, gimple_cond_rhs (stmt)); | |
2abae5f1 | 348 | |
36f40be0 | 349 | isl_set *cond; |
33ad93b9 | 350 | switch (code) |
2abae5f1 | 351 | { |
33ad93b9 RG |
352 | case LT_EXPR: |
353 | cond = isl_pw_aff_lt_set (lhs, rhs); | |
354 | break; | |
2abae5f1 | 355 | |
33ad93b9 RG |
356 | case GT_EXPR: |
357 | cond = isl_pw_aff_gt_set (lhs, rhs); | |
358 | break; | |
2abae5f1 | 359 | |
33ad93b9 RG |
360 | case LE_EXPR: |
361 | cond = isl_pw_aff_le_set (lhs, rhs); | |
362 | break; | |
2abae5f1 | 363 | |
33ad93b9 RG |
364 | case GE_EXPR: |
365 | cond = isl_pw_aff_ge_set (lhs, rhs); | |
366 | break; | |
2abae5f1 | 367 | |
33ad93b9 RG |
368 | case EQ_EXPR: |
369 | cond = isl_pw_aff_eq_set (lhs, rhs); | |
370 | break; | |
2abae5f1 | 371 | |
33ad93b9 RG |
372 | case NE_EXPR: |
373 | cond = isl_pw_aff_ne_set (lhs, rhs); | |
374 | break; | |
2abae5f1 | 375 | |
33ad93b9 | 376 | default: |
adba512d | 377 | gcc_unreachable (); |
2abae5f1 | 378 | } |
33ad93b9 RG |
379 | |
380 | cond = isl_set_coalesce (cond); | |
381 | cond = isl_set_set_tuple_id (cond, isl_set_get_tuple_id (pbb->domain)); | |
14b1747c | 382 | pbb->domain = isl_set_coalesce (isl_set_intersect (pbb->domain, cond)); |
2abae5f1 SP |
383 | } |
384 | ||
385 | /* Add conditions to the domain of PBB. */ | |
386 | ||
adba512d | 387 | static void |
2abae5f1 SP |
388 | add_conditions_to_domain (poly_bb_p pbb) |
389 | { | |
390 | unsigned int i; | |
355fe088 | 391 | gimple *stmt; |
65ef70d6 | 392 | gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); |
2abae5f1 | 393 | |
9771b263 | 394 | if (GBB_CONDITIONS (gbb).is_empty ()) |
adba512d | 395 | return; |
2abae5f1 | 396 | |
9771b263 | 397 | FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt) |
2abae5f1 SP |
398 | switch (gimple_code (stmt)) |
399 | { | |
400 | case GIMPLE_COND: | |
401 | { | |
4bc4dd11 AK |
402 | /* Don't constrain on anything else than INTEGER_TYPE. */ |
403 | if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt))) != INTEGER_TYPE) | |
404 | break; | |
405 | ||
538dd0b7 DM |
406 | gcond *cond_stmt = as_a <gcond *> (stmt); |
407 | enum tree_code code = gimple_cond_code (cond_stmt); | |
2abae5f1 SP |
408 | |
409 | /* The conditions for ELSE-branches are inverted. */ | |
9771b263 | 410 | if (!GBB_CONDITION_CASES (gbb)[i]) |
2abae5f1 SP |
411 | code = invert_tree_comparison (code, false); |
412 | ||
adba512d | 413 | add_condition_to_pbb (pbb, cond_stmt, code); |
2abae5f1 SP |
414 | break; |
415 | } | |
416 | ||
2abae5f1 SP |
417 | default: |
418 | gcc_unreachable (); | |
419 | break; | |
420 | } | |
efa21390 SP |
421 | } |
422 | ||
2abae5f1 SP |
423 | /* Add constraints on the possible values of parameter P from the type |
424 | of P. */ | |
425 | ||
426 | static void | |
33ad93b9 | 427 | add_param_constraints (scop_p scop, graphite_dim_t p) |
2abae5f1 | 428 | { |
65b016eb | 429 | tree parameter = scop->scop_info->params[p]; |
2abae5f1 | 430 | tree type = TREE_TYPE (parameter); |
3640d64c SP |
431 | tree lb = NULL_TREE; |
432 | tree ub = NULL_TREE; | |
2abae5f1 | 433 | |
697f511d SP |
434 | if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type)) |
435 | lb = lower_bound_in_type (type, type); | |
436 | else | |
437 | lb = TYPE_MIN_VALUE (type); | |
438 | ||
439 | if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type)) | |
440 | ub = upper_bound_in_type (type, type); | |
441 | else | |
442 | ub = TYPE_MAX_VALUE (type); | |
2abae5f1 SP |
443 | |
444 | if (lb) | |
445 | { | |
8e4dc590 | 446 | isl_space *space = isl_set_get_space (scop->param_context); |
33ad93b9 | 447 | isl_constraint *c; |
b47595f7 | 448 | isl_val *v; |
33ad93b9 RG |
449 | |
450 | c = isl_inequality_alloc (isl_local_space_from_space (space)); | |
cc46a51d | 451 | v = isl_val_int_from_wi (scop->isl_context, wi::to_widest (lb)); |
b47595f7 | 452 | v = isl_val_neg (v); |
b47595f7 | 453 | c = isl_constraint_set_constant_val (c, v); |
33ad93b9 RG |
454 | c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, 1); |
455 | ||
14b1747c AK |
456 | scop->param_context = isl_set_coalesce |
457 | (isl_set_add_constraint (scop->param_context, c)); | |
2abae5f1 SP |
458 | } |
459 | ||
460 | if (ub) | |
461 | { | |
8e4dc590 | 462 | isl_space *space = isl_set_get_space (scop->param_context); |
33ad93b9 | 463 | isl_constraint *c; |
b47595f7 | 464 | isl_val *v; |
33ad93b9 RG |
465 | |
466 | c = isl_inequality_alloc (isl_local_space_from_space (space)); | |
467 | ||
cc46a51d | 468 | v = isl_val_int_from_wi (scop->isl_context, wi::to_widest (ub)); |
b47595f7 | 469 | c = isl_constraint_set_constant_val (c, v); |
33ad93b9 RG |
470 | c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, -1); |
471 | ||
14b1747c AK |
472 | scop->param_context = isl_set_coalesce |
473 | (isl_set_add_constraint (scop->param_context, c)); | |
2abae5f1 SP |
474 | } |
475 | } | |
476 | ||
2abae5f1 SP |
477 | /* Add a constrain to the ACCESSES polyhedron for the alias set of |
478 | data reference DR. ACCESSP_NB_DIMS is the dimension of the | |
479 | ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration | |
480 | domain. */ | |
481 | ||
33ad93b9 | 482 | static isl_map * |
09fefdad | 483 | pdr_add_alias_set (isl_map *acc, dr_info &dri) |
2abae5f1 | 484 | { |
790befae | 485 | isl_constraint *c = isl_equality_alloc |
33ad93b9 | 486 | (isl_local_space_from_space (isl_map_get_space (acc))); |
65b016eb | 487 | /* Positive numbers for all alias sets. */ |
09fefdad | 488 | c = isl_constraint_set_constant_si (c, -dri.alias_set); |
33ad93b9 RG |
489 | c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1); |
490 | ||
491 | return isl_map_add_constraint (acc, c); | |
492 | } | |
493 | ||
65b016eb AK |
494 | /* Add a constrain to the ACCESSES polyhedron for the alias set of |
495 | data reference DR. ACCESSP_NB_DIMS is the dimension of the | |
496 | ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration | |
497 | domain. */ | |
498 | ||
499 | static isl_map * | |
500 | add_scalar_version_numbers (isl_map *acc, tree var) | |
501 | { | |
502 | isl_constraint *c = isl_equality_alloc | |
503 | (isl_local_space_from_space (isl_map_get_space (acc))); | |
504 | int max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP); | |
505 | /* Each scalar variables has a unique alias set number starting from | |
506 | max_arrays. */ | |
507 | c = isl_constraint_set_constant_si (c, -max_arrays - SSA_NAME_VERSION (var)); | |
508 | c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1); | |
509 | ||
510 | return isl_map_add_constraint (acc, c); | |
511 | } | |
512 | ||
33ad93b9 RG |
513 | /* Assign the affine expression INDEX to the output dimension POS of |
514 | MAP and return the result. */ | |
515 | ||
516 | static isl_map * | |
517 | set_index (isl_map *map, int pos, isl_pw_aff *index) | |
518 | { | |
519 | isl_map *index_map; | |
520 | int len = isl_map_dim (map, isl_dim_out); | |
521 | isl_id *id; | |
522 | ||
523 | index_map = isl_map_from_pw_aff (index); | |
524 | index_map = isl_map_insert_dims (index_map, isl_dim_out, 0, pos); | |
525 | index_map = isl_map_add_dims (index_map, isl_dim_out, len - pos - 1); | |
2abae5f1 | 526 | |
33ad93b9 RG |
527 | id = isl_map_get_tuple_id (map, isl_dim_out); |
528 | index_map = isl_map_set_tuple_id (index_map, isl_dim_out, id); | |
529 | id = isl_map_get_tuple_id (map, isl_dim_in); | |
530 | index_map = isl_map_set_tuple_id (index_map, isl_dim_in, id); | |
2abae5f1 | 531 | |
33ad93b9 | 532 | return isl_map_intersect (map, index_map); |
2abae5f1 SP |
533 | } |
534 | ||
535 | /* Add to ACCESSES polyhedron equalities defining the access functions | |
536 | to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES | |
537 | polyhedron, DOM_NB_DIMS is the dimension of the iteration domain. | |
538 | PBB is the poly_bb_p that contains the data reference DR. */ | |
539 | ||
33ad93b9 | 540 | static isl_map * |
09fefdad | 541 | pdr_add_memory_accesses (isl_map *acc, dr_info &dri) |
2abae5f1 | 542 | { |
09fefdad AK |
543 | data_reference_p dr = dri.dr; |
544 | poly_bb_p pbb = dri.pbb; | |
2abae5f1 | 545 | int i, nb_subscripts = DR_NUM_DIMENSIONS (dr); |
2abae5f1 | 546 | scop_p scop = PBB_SCOP (pbb); |
2abae5f1 SP |
547 | |
548 | for (i = 0; i < nb_subscripts; i++) | |
549 | { | |
33ad93b9 | 550 | isl_pw_aff *aff; |
ce6a2c92 | 551 | tree afn = DR_ACCESS_FN (dr, i); |
2abae5f1 | 552 | |
33ad93b9 RG |
553 | aff = extract_affine (scop, afn, |
554 | isl_space_domain (isl_map_get_space (acc))); | |
09bf990e | 555 | acc = set_index (acc, nb_subscripts - i , aff); |
2abae5f1 SP |
556 | } |
557 | ||
14b1747c | 558 | return isl_map_coalesce (acc); |
2abae5f1 SP |
559 | } |
560 | ||
2e733703 AK |
561 | /* Return true when the LOW and HIGH bounds of an array reference REF are valid |
562 | to extract constraints on accessed elements of the array. Returning false is | |
563 | the conservative answer. */ | |
564 | ||
565 | static bool | |
566 | bounds_are_valid (tree ref, tree low, tree high) | |
567 | { | |
568 | if (!high) | |
569 | return false; | |
570 | ||
571 | if (!tree_fits_shwi_p (low) | |
572 | || !tree_fits_shwi_p (high)) | |
573 | return false; | |
574 | ||
575 | /* 1-element arrays at end of structures may extend over | |
576 | their declared size. */ | |
577 | if (array_at_struct_end_p (ref) | |
578 | && operand_equal_p (low, high, 0)) | |
579 | return false; | |
580 | ||
581 | /* Fortran has some arrays where high bound is -1 and low is 0. */ | |
582 | if (integer_onep (fold_build2 (LT_EXPR, boolean_type_node, high, low))) | |
583 | return false; | |
584 | ||
585 | return true; | |
586 | } | |
587 | ||
2abae5f1 | 588 | /* Add constrains representing the size of the accessed data to the |
66096911 SP |
589 | ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the |
590 | ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration | |
2abae5f1 SP |
591 | domain. */ |
592 | ||
33ad93b9 | 593 | static isl_set * |
24757752 AK |
594 | pdr_add_data_dimensions (isl_set *subscript_sizes, scop_p scop, |
595 | data_reference_p dr) | |
2abae5f1 SP |
596 | { |
597 | tree ref = DR_REF (dr); | |
2abae5f1 | 598 | |
24757752 AK |
599 | int nb_subscripts = DR_NUM_DIMENSIONS (dr); |
600 | for (int i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0)) | |
2abae5f1 | 601 | { |
98f3eb1f | 602 | if (TREE_CODE (ref) != ARRAY_REF) |
24757752 | 603 | return subscript_sizes; |
2abae5f1 | 604 | |
24757752 AK |
605 | tree low = array_ref_low_bound (ref); |
606 | tree high = array_ref_up_bound (ref); | |
98f3eb1f | 607 | |
2e733703 AK |
608 | if (!bounds_are_valid (ref, low, high)) |
609 | continue; | |
610 | ||
611 | isl_space *space = isl_set_get_space (subscript_sizes); | |
612 | isl_pw_aff *lb = extract_affine_int (low, isl_space_copy (space)); | |
613 | isl_pw_aff *ub = extract_affine_int (high, isl_space_copy (space)); | |
614 | ||
615 | /* high >= 0 */ | |
616 | isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub)); | |
617 | valid = isl_set_project_out (valid, isl_dim_set, 0, | |
618 | isl_set_dim (valid, isl_dim_set)); | |
14b1747c AK |
619 | scop->param_context = isl_set_coalesce |
620 | (isl_set_intersect (scop->param_context, valid)); | |
2e733703 AK |
621 | |
622 | isl_aff *aff | |
623 | = isl_aff_zero_on_domain (isl_local_space_from_space (space)); | |
624 | aff = isl_aff_add_coefficient_si (aff, isl_dim_in, i + 1, 1); | |
625 | isl_set *univ | |
626 | = isl_set_universe (isl_space_domain (isl_aff_get_space (aff))); | |
627 | isl_pw_aff *index = isl_pw_aff_alloc (univ, aff); | |
628 | ||
629 | isl_id *id = isl_set_get_tuple_id (subscript_sizes); | |
630 | lb = isl_pw_aff_set_tuple_id (lb, isl_dim_in, isl_id_copy (id)); | |
631 | ub = isl_pw_aff_set_tuple_id (ub, isl_dim_in, id); | |
632 | ||
633 | /* low <= sub_i <= high */ | |
634 | isl_set *lbs = isl_pw_aff_ge_set (isl_pw_aff_copy (index), lb); | |
635 | isl_set *ubs = isl_pw_aff_le_set (index, ub); | |
636 | subscript_sizes = isl_set_intersect (subscript_sizes, lbs); | |
637 | subscript_sizes = isl_set_intersect (subscript_sizes, ubs); | |
2abae5f1 | 638 | } |
33ad93b9 | 639 | |
14b1747c | 640 | return isl_set_coalesce (subscript_sizes); |
2abae5f1 SP |
641 | } |
642 | ||
65b016eb | 643 | /* Build data accesses for DRI. */ |
2abae5f1 SP |
644 | |
645 | static void | |
09fefdad | 646 | build_poly_dr (dr_info &dri) |
2abae5f1 | 647 | { |
33ad93b9 | 648 | isl_map *acc; |
24757752 | 649 | isl_set *subscript_sizes; |
09fefdad AK |
650 | poly_bb_p pbb = dri.pbb; |
651 | data_reference_p dr = dri.dr; | |
33ad93b9 | 652 | scop_p scop = PBB_SCOP (pbb); |
65b016eb | 653 | isl_id *id = isl_id_for_dr (scop); |
2abae5f1 | 654 | |
33ad93b9 RG |
655 | { |
656 | isl_space *dc = isl_set_get_space (pbb->domain); | |
657 | int nb_out = 1 + DR_NUM_DIMENSIONS (dr); | |
658 | isl_space *space = isl_space_add_dims (isl_space_from_domain (dc), | |
659 | isl_dim_out, nb_out); | |
2abae5f1 | 660 | |
33ad93b9 | 661 | acc = isl_map_universe (space); |
65b016eb | 662 | acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_copy (id)); |
33ad93b9 | 663 | } |
2abae5f1 | 664 | |
09fefdad AK |
665 | acc = pdr_add_alias_set (acc, dri); |
666 | acc = pdr_add_memory_accesses (acc, dri); | |
2abae5f1 | 667 | |
33ad93b9 | 668 | { |
33ad93b9 | 669 | int nb = 1 + DR_NUM_DIMENSIONS (dr); |
8e4dc590 | 670 | isl_space *space = isl_space_set_alloc (scop->isl_context, 0, nb); |
33ad93b9 RG |
671 | |
672 | space = isl_space_set_tuple_id (space, isl_dim_set, id); | |
24757752 AK |
673 | subscript_sizes = isl_set_nat_universe (space); |
674 | subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0, | |
09fefdad | 675 | dri.alias_set); |
24757752 | 676 | subscript_sizes = pdr_add_data_dimensions (subscript_sizes, scop, dr); |
33ad93b9 | 677 | } |
2abae5f1 | 678 | |
65b016eb AK |
679 | new_poly_dr (pbb, DR_STMT (dr), DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, |
680 | acc, subscript_sizes); | |
2abae5f1 SP |
681 | } |
682 | ||
278b1a1d | 683 | static void |
65b016eb AK |
684 | build_poly_sr_1 (poly_bb_p pbb, gimple *stmt, tree var, enum poly_dr_type kind, |
685 | isl_map *acc, isl_set *subscript_sizes) | |
278b1a1d | 686 | { |
65b016eb AK |
687 | int max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP); |
688 | /* Each scalar variables has a unique alias set number starting from | |
689 | max_arrays. */ | |
690 | subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0, | |
691 | max_arrays + SSA_NAME_VERSION (var)); | |
692 | ||
693 | new_poly_dr (pbb, stmt, kind, add_scalar_version_numbers (acc, var), | |
694 | subscript_sizes); | |
278b1a1d SP |
695 | } |
696 | ||
65b016eb | 697 | /* Record all cross basic block scalar variables in PBB. */ |
2abae5f1 SP |
698 | |
699 | static void | |
65b016eb | 700 | build_poly_sr (poly_bb_p pbb) |
2abae5f1 | 701 | { |
65b016eb | 702 | scop_p scop = PBB_SCOP (pbb); |
65ef70d6 | 703 | gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); |
0ddb9c8d AK |
704 | vec<scalar_use> &reads = gbb->read_scalar_refs; |
705 | vec<tree> &writes = gbb->write_scalar_refs; | |
1c2a7491 | 706 | |
65b016eb AK |
707 | isl_space *dc = isl_set_get_space (pbb->domain); |
708 | int nb_out = 1; | |
709 | isl_space *space = isl_space_add_dims (isl_space_from_domain (dc), | |
710 | isl_dim_out, nb_out); | |
711 | isl_id *id = isl_id_for_dr (scop); | |
712 | space = isl_space_set_tuple_id (space, isl_dim_set, isl_id_copy (id)); | |
713 | isl_map *acc = isl_map_universe (isl_space_copy (space)); | |
714 | acc = isl_map_set_tuple_id (acc, isl_dim_out, id); | |
715 | isl_set *subscript_sizes = isl_set_nat_universe (space); | |
9773d730 | 716 | |
caf5b4df | 717 | int i; |
65b016eb AK |
718 | tree var; |
719 | FOR_EACH_VEC_ELT (writes, i, var) | |
720 | build_poly_sr_1 (pbb, SSA_NAME_DEF_STMT (var), var, PDR_WRITE, | |
721 | isl_map_copy (acc), isl_set_copy (subscript_sizes)); | |
5d737345 | 722 | |
65b016eb AK |
723 | scalar_use *use; |
724 | FOR_EACH_VEC_ELT (reads, i, use) | |
725 | build_poly_sr_1 (pbb, use->first, use->second, PDR_READ, isl_map_copy (acc), | |
726 | isl_set_copy (subscript_sizes)); | |
d5b5a232 | 727 | |
65b016eb AK |
728 | isl_map_free (acc); |
729 | isl_set_free (subscript_sizes); | |
5dcc64d9 SP |
730 | } |
731 | ||
65b016eb | 732 | /* Build data references in SCOP. */ |
ee646fc6 | 733 | |
efa21390 | 734 | static void |
65b016eb | 735 | build_scop_drs (scop_p scop) |
ee646fc6 | 736 | { |
caf5b4df | 737 | int i; |
65b016eb AK |
738 | dr_info *dri; |
739 | FOR_EACH_VEC_ELT (scop->drs, i, dri) | |
740 | build_poly_dr (*dri); | |
5dcc64d9 | 741 | |
65b016eb AK |
742 | poly_bb_p pbb; |
743 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) | |
744 | build_poly_sr (pbb); | |
2abae5f1 SP |
745 | } |
746 | ||
adba512d AK |
747 | /* Add to the iteration DOMAIN one extra dimension for LOOP->num. */ |
748 | ||
749 | static isl_set * | |
750 | add_iter_domain_dimension (__isl_take isl_set *domain, loop_p loop, scop_p scop) | |
751 | { | |
752 | int loop_index = isl_set_dim (domain, isl_dim_set); | |
753 | domain = isl_set_add_dims (domain, isl_dim_set, 1); | |
754 | char name[50]; | |
755 | snprintf (name, sizeof(name), "i%d", loop->num); | |
756 | isl_id *label = isl_id_alloc (scop->isl_context, name, NULL); | |
757 | return isl_set_set_dim_id (domain, isl_dim_set, loop_index, label); | |
758 | } | |
759 | ||
d8d262cf AK |
760 | /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */ |
761 | ||
762 | static isl_set * | |
763 | add_loop_constraints (scop_p scop, __isl_take isl_set *domain, loop_p loop, | |
764 | loop_p context) | |
765 | { | |
766 | if (loop == context) | |
767 | return domain; | |
768 | const sese_l ®ion = scop->scop_info->region; | |
769 | if (!loop_in_sese_p (loop, region)) | |
770 | return domain; | |
771 | ||
772 | /* Recursion all the way up to the context loop. */ | |
773 | domain = add_loop_constraints (scop, domain, loop_outer (loop), context); | |
774 | ||
775 | /* Then, build constraints over the loop in post-order: outer to inner. */ | |
776 | ||
777 | int loop_index = isl_set_dim (domain, isl_dim_set); | |
778 | if (dump_file) | |
779 | fprintf (dump_file, "[sese-to-poly] adding one extra dimension to the " | |
780 | "domain for loop_%d.\n", loop->num); | |
adba512d | 781 | domain = add_iter_domain_dimension (domain, loop, scop); |
d8d262cf AK |
782 | isl_space *space = isl_set_get_space (domain); |
783 | ||
784 | /* 0 <= loop_i */ | |
785 | isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space)); | |
786 | isl_constraint *c = isl_inequality_alloc (ls); | |
787 | c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, 1); | |
788 | if (dump_file) | |
789 | { | |
790 | fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: "); | |
791 | print_isl_constraint (dump_file, c); | |
792 | } | |
793 | domain = isl_set_add_constraint (domain, c); | |
794 | ||
795 | tree nb_iters = number_of_latch_executions (loop); | |
796 | if (TREE_CODE (nb_iters) == INTEGER_CST) | |
797 | { | |
798 | /* loop_i <= cst_nb_iters */ | |
799 | isl_local_space *ls = isl_local_space_from_space (space); | |
800 | isl_constraint *c = isl_inequality_alloc (ls); | |
801 | c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1); | |
cc46a51d RB |
802 | isl_val *v |
803 | = isl_val_int_from_wi (scop->isl_context, wi::to_widest (nb_iters)); | |
d8d262cf AK |
804 | c = isl_constraint_set_constant_val (c, v); |
805 | return isl_set_add_constraint (domain, c); | |
806 | } | |
807 | /* loop_i <= expr_nb_iters */ | |
808 | gcc_assert (!chrec_contains_undetermined (nb_iters)); | |
809 | nb_iters = scalar_evolution_in_region (region, loop, nb_iters); | |
810 | gcc_assert (!chrec_contains_undetermined (nb_iters)); | |
811 | ||
812 | isl_pw_aff *aff_nb_iters = extract_affine (scop, nb_iters, | |
813 | isl_space_copy (space)); | |
814 | isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters)); | |
815 | valid = isl_set_project_out (valid, isl_dim_set, 0, | |
816 | isl_set_dim (valid, isl_dim_set)); | |
817 | ||
818 | if (valid) | |
819 | scop->param_context = isl_set_intersect (scop->param_context, valid); | |
820 | ||
821 | ls = isl_local_space_from_space (isl_space_copy (space)); | |
822 | isl_aff *loop_i = isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls), | |
823 | isl_dim_in, loop_index, 1); | |
824 | isl_set *le = isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i), | |
825 | isl_pw_aff_copy (aff_nb_iters)); | |
826 | if (dump_file) | |
827 | { | |
828 | fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: "); | |
829 | print_isl_set (dump_file, le); | |
830 | } | |
831 | domain = isl_set_intersect (domain, le); | |
832 | ||
833 | widest_int nit; | |
834 | if (!max_stmt_executions (loop, &nit)) | |
835 | { | |
836 | isl_pw_aff_free (aff_nb_iters); | |
837 | isl_space_free (space); | |
838 | return domain; | |
839 | } | |
840 | ||
841 | /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we | |
842 | do not know whether the loop executes at least once. */ | |
cc46a51d | 843 | --nit; |
d8d262cf | 844 | |
cc46a51d | 845 | isl_pw_aff *approx = extract_affine_wi (nit, isl_space_copy (space)); |
d8d262cf AK |
846 | isl_set *x = isl_pw_aff_ge_set (approx, aff_nb_iters); |
847 | x = isl_set_project_out (x, isl_dim_set, 0, | |
848 | isl_set_dim (x, isl_dim_set)); | |
849 | scop->param_context = isl_set_intersect (scop->param_context, x); | |
850 | ||
851 | ls = isl_local_space_from_space (space); | |
852 | c = isl_inequality_alloc (ls); | |
853 | c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1); | |
cc46a51d | 854 | isl_val *v = isl_val_int_from_wi (scop->isl_context, nit); |
d8d262cf AK |
855 | c = isl_constraint_set_constant_val (c, v); |
856 | ||
857 | if (dump_file) | |
858 | { | |
859 | fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: "); | |
860 | print_isl_constraint (dump_file, c); | |
861 | } | |
862 | ||
863 | return isl_set_add_constraint (domain, c); | |
864 | } | |
865 | ||
866 | /* Builds the original iteration domains for each pbb in the SCOP. */ | |
867 | ||
868 | static int | |
adba512d AK |
869 | build_iteration_domains (scop_p scop, __isl_keep isl_set *context, |
870 | int index, loop_p context_loop) | |
d8d262cf AK |
871 | { |
872 | loop_p current = pbb_loop (scop->pbbs[index]); | |
873 | isl_set *domain = isl_set_copy (context); | |
874 | domain = add_loop_constraints (scop, domain, current, context_loop); | |
875 | const sese_l ®ion = scop->scop_info->region; | |
876 | ||
877 | int i; | |
878 | poly_bb_p pbb; | |
879 | FOR_EACH_VEC_ELT_FROM (scop->pbbs, i, pbb, index) | |
880 | { | |
881 | loop_p loop = pbb_loop (pbb); | |
882 | if (current == loop) | |
883 | { | |
adba512d | 884 | pbb->iterators = isl_set_copy (domain); |
d8d262cf AK |
885 | pbb->domain = isl_set_copy (domain); |
886 | pbb->domain = isl_set_set_tuple_id (pbb->domain, | |
887 | isl_id_for_pbb (scop, pbb)); | |
adba512d AK |
888 | add_conditions_to_domain (pbb); |
889 | ||
d8d262cf AK |
890 | if (dump_file) |
891 | { | |
892 | fprintf (dump_file, "[sese-to-poly] set pbb_%d->domain: ", | |
893 | pbb_index (pbb)); | |
894 | print_isl_set (dump_file, domain); | |
895 | } | |
896 | continue; | |
897 | } | |
898 | ||
899 | while (loop_in_sese_p (loop, region) | |
900 | && current != loop) | |
901 | loop = loop_outer (loop); | |
902 | ||
903 | if (current != loop) | |
904 | { | |
905 | /* A statement in a different loop nest than CURRENT loop. */ | |
906 | isl_set_free (domain); | |
907 | return i; | |
908 | } | |
909 | ||
910 | /* A statement nested in the CURRENT loop. */ | |
911 | i = build_iteration_domains (scop, domain, i, current); | |
912 | i--; | |
913 | } | |
914 | ||
915 | isl_set_free (domain); | |
916 | return i; | |
917 | } | |
918 | ||
d8d262cf AK |
919 | /* Assign dimension for each parameter in SCOP and add constraints for the |
920 | parameters. */ | |
921 | ||
922 | static void | |
923 | build_scop_context (scop_p scop) | |
924 | { | |
925 | sese_info_p region = scop->scop_info; | |
926 | unsigned nbp = sese_nb_params (region); | |
927 | isl_space *space = isl_space_set_alloc (scop->isl_context, nbp, 0); | |
928 | ||
929 | unsigned i; | |
930 | tree e; | |
931 | FOR_EACH_VEC_ELT (region->params, i, e) | |
932 | space = isl_space_set_dim_id (space, isl_dim_param, i, | |
933 | isl_id_for_ssa_name (scop, e)); | |
934 | ||
935 | scop->param_context = isl_set_universe (space); | |
936 | ||
937 | graphite_dim_t p; | |
938 | for (p = 0; p < nbp; p++) | |
939 | add_param_constraints (scop, p); | |
940 | } | |
941 | ||
adba512d AK |
942 | /* Return true when loop A is nested in loop B. */ |
943 | ||
944 | static bool | |
945 | nested_in (loop_p a, loop_p b) | |
946 | { | |
947 | return b == find_common_loop (a, b); | |
948 | } | |
949 | ||
950 | /* Return the loop at a specific SCOP->pbbs[*INDEX]. */ | |
951 | static loop_p | |
952 | loop_at (scop_p scop, int *index) | |
953 | { | |
954 | return pbb_loop (scop->pbbs[*index]); | |
955 | } | |
956 | ||
957 | /* Return the index of any pbb belonging to loop or a subloop of A. */ | |
958 | ||
959 | static int | |
960 | index_outermost_in_loop (loop_p a, scop_p scop) | |
961 | { | |
962 | int i, outermost = -1; | |
963 | int last_depth = -1; | |
964 | poly_bb_p pbb; | |
965 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) | |
966 | if (nested_in (pbb_loop (pbb), a) | |
967 | && (last_depth == -1 | |
968 | || last_depth > (int) loop_depth (pbb_loop (pbb)))) | |
969 | { | |
970 | outermost = i; | |
971 | last_depth = loop_depth (pbb_loop (pbb)); | |
972 | } | |
973 | return outermost; | |
974 | } | |
975 | ||
976 | /* Return the index of any pbb belonging to loop or a subloop of A. */ | |
977 | ||
978 | static int | |
979 | index_pbb_in_loop (loop_p a, scop_p scop) | |
980 | { | |
981 | int i; | |
982 | poly_bb_p pbb; | |
983 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) | |
984 | if (pbb_loop (pbb) == a) | |
985 | return i; | |
986 | return -1; | |
987 | } | |
988 | ||
989 | static poly_bb_p | |
990 | outermost_pbb_in (loop_p loop, scop_p scop) | |
991 | { | |
992 | int x = index_pbb_in_loop (loop, scop); | |
993 | if (x == -1) | |
994 | x = index_outermost_in_loop (loop, scop); | |
995 | return scop->pbbs[x]; | |
996 | } | |
997 | ||
998 | static isl_schedule * | |
999 | add_in_sequence (__isl_take isl_schedule *a, __isl_take isl_schedule *b) | |
1000 | { | |
1001 | gcc_assert (a || b); | |
1002 | ||
1003 | if (!a) | |
1004 | return b; | |
1005 | ||
1006 | if (!b) | |
1007 | return a; | |
1008 | ||
1009 | return isl_schedule_sequence (a, b); | |
1010 | } | |
1011 | ||
1012 | struct map_to_dimension_data { | |
1013 | int n; | |
1014 | isl_union_pw_multi_aff *res; | |
1015 | }; | |
1016 | ||
1017 | /* Create a function that maps the elements of SET to its N-th dimension and add | |
1018 | it to USER->res. */ | |
1019 | ||
1020 | static isl_stat | |
1021 | add_outer_projection (__isl_take isl_set *set, void *user) | |
1022 | { | |
1023 | struct map_to_dimension_data *data = (struct map_to_dimension_data *) user; | |
1024 | int dim = isl_set_dim (set, isl_dim_set); | |
1025 | isl_space *space = isl_set_get_space (set); | |
1026 | ||
1027 | gcc_assert (dim >= data->n); | |
1028 | isl_pw_multi_aff *pma | |
1029 | = isl_pw_multi_aff_project_out_map (space, isl_dim_set, data->n, | |
1030 | dim - data->n); | |
1031 | data->res = isl_union_pw_multi_aff_add_pw_multi_aff (data->res, pma); | |
1032 | ||
1033 | isl_set_free (set); | |
1034 | return isl_stat_ok; | |
1035 | } | |
1036 | ||
1037 | /* Return SET in which all inner dimensions above N are removed. */ | |
1038 | ||
1039 | static isl_multi_union_pw_aff * | |
1040 | outer_projection_mupa (__isl_take isl_union_set *set, int n) | |
1041 | { | |
1042 | gcc_assert (n >= 0); | |
1043 | gcc_assert (set); | |
1044 | gcc_assert (!isl_union_set_is_empty (set)); | |
1045 | ||
1046 | isl_space *space = isl_union_set_get_space (set); | |
1047 | isl_union_pw_multi_aff *pwaff = isl_union_pw_multi_aff_empty (space); | |
1048 | ||
1049 | struct map_to_dimension_data data = {n, pwaff}; | |
1050 | ||
1051 | if (isl_union_set_foreach_set (set, &add_outer_projection, &data) < 0) | |
1052 | data.res = isl_union_pw_multi_aff_free (data.res); | |
1053 | ||
1054 | isl_union_set_free (set); | |
1055 | return isl_multi_union_pw_aff_from_union_pw_multi_aff (data.res); | |
1056 | } | |
1057 | ||
197d2f5b RB |
1058 | static bool schedule_error; |
1059 | ||
adba512d AK |
1060 | /* Embed SCHEDULE in the constraints of the LOOP domain. */ |
1061 | ||
1062 | static isl_schedule * | |
1063 | add_loop_schedule (__isl_take isl_schedule *schedule, loop_p loop, | |
1064 | scop_p scop) | |
1065 | { | |
1066 | poly_bb_p pbb = outermost_pbb_in (loop, scop); | |
1067 | isl_set *iterators = pbb->iterators; | |
1068 | ||
1069 | int empty = isl_set_is_empty (iterators); | |
1070 | if (empty < 0 || empty) | |
1071 | return empty < 0 ? isl_schedule_free (schedule) : schedule; | |
1072 | ||
197d2f5b RB |
1073 | isl_union_set *domain = isl_schedule_get_domain (schedule); |
1074 | /* We cannot apply an empty domain to pbbs in this loop so fail. | |
1075 | ??? Somehow drop pbbs in the loop instead. */ | |
1076 | if (isl_union_set_is_empty (domain)) | |
1077 | { | |
1078 | schedule_error = true; | |
1079 | isl_union_set_free (domain); | |
1080 | return schedule; | |
1081 | } | |
1082 | ||
adba512d AK |
1083 | isl_space *space = isl_set_get_space (iterators); |
1084 | int loop_index = isl_space_dim (space, isl_dim_set) - 1; | |
1085 | ||
1086 | loop_p ploop = pbb_loop (pbb); | |
1087 | while (loop != ploop) | |
1088 | { | |
1089 | --loop_index; | |
1090 | ploop = loop_outer (ploop); | |
1091 | } | |
1092 | ||
1093 | isl_local_space *ls = isl_local_space_from_space (space); | |
1094 | isl_aff *aff = isl_aff_var_on_domain (ls, isl_dim_set, loop_index); | |
1095 | isl_multi_aff *prefix = isl_multi_aff_from_aff (aff); | |
1096 | char name[50]; | |
1097 | snprintf (name, sizeof(name), "L_%d", loop->num); | |
1098 | isl_id *label = isl_id_alloc (isl_schedule_get_ctx (schedule), | |
1099 | name, NULL); | |
1100 | prefix = isl_multi_aff_set_tuple_id (prefix, isl_dim_out, label); | |
1101 | ||
1102 | int n = isl_multi_aff_dim (prefix, isl_dim_in); | |
adba512d AK |
1103 | isl_multi_union_pw_aff *mupa = outer_projection_mupa (domain, n); |
1104 | mupa = isl_multi_union_pw_aff_apply_multi_aff (mupa, prefix); | |
1105 | return isl_schedule_insert_partial_schedule (schedule, mupa); | |
1106 | } | |
1107 | ||
1108 | /* Build schedule for the pbb at INDEX. */ | |
1109 | ||
1110 | static isl_schedule * | |
1111 | build_schedule_pbb (scop_p scop, int *index) | |
1112 | { | |
1113 | poly_bb_p pbb = scop->pbbs[*index]; | |
1114 | ++*index; | |
1115 | isl_set *domain = isl_set_copy (pbb->domain); | |
1116 | isl_union_set *ud = isl_union_set_from_set (domain); | |
1117 | return isl_schedule_from_domain (ud); | |
1118 | } | |
1119 | ||
1120 | static isl_schedule *build_schedule_loop_nest (scop_p, int *, loop_p); | |
1121 | ||
1122 | /* Build the schedule of the loop containing the SCOP pbb at INDEX. */ | |
1123 | ||
1124 | static isl_schedule * | |
1125 | build_schedule_loop (scop_p scop, int *index) | |
1126 | { | |
1127 | int max = scop->pbbs.length (); | |
1128 | gcc_assert (*index < max); | |
1129 | loop_p loop = loop_at (scop, index); | |
1130 | ||
1131 | isl_schedule *s = NULL; | |
1132 | while (nested_in (loop_at (scop, index), loop)) | |
1133 | { | |
1134 | if (loop == loop_at (scop, index)) | |
1135 | s = add_in_sequence (s, build_schedule_pbb (scop, index)); | |
1136 | else | |
1137 | s = add_in_sequence (s, build_schedule_loop_nest (scop, index, loop)); | |
1138 | ||
1139 | if (*index == max) | |
1140 | break; | |
1141 | } | |
1142 | ||
1143 | return add_loop_schedule (s, loop, scop); | |
1144 | } | |
1145 | ||
1146 | /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops. | |
1147 | When CONTEXT_LOOP is null, embed the schedule in all loops contained in the | |
1148 | SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the | |
1149 | maximal loop nest contained within CONTEXT_LOOP. */ | |
1150 | ||
1151 | static isl_schedule * | |
1152 | embed_in_surrounding_loops (__isl_take isl_schedule *s, scop_p scop, | |
1153 | loop_p loop, int *index, loop_p context_loop) | |
1154 | { | |
1155 | loop_p outer = loop_outer (loop); | |
1156 | sese_l region = scop->scop_info->region; | |
1157 | if (context_loop == outer | |
1158 | || !loop_in_sese_p (outer, region)) | |
1159 | return s; | |
1160 | ||
1161 | int max = scop->pbbs.length (); | |
1162 | if (*index == max | |
1163 | || (context_loop && !nested_in (loop_at (scop, index), context_loop)) | |
1164 | || (!context_loop | |
1165 | && !loop_in_sese_p (find_common_loop (outer, loop_at (scop, index)), | |
1166 | region))) | |
1167 | return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop), | |
1168 | scop, outer, index, context_loop); | |
1169 | ||
1170 | bool a_pbb; | |
1171 | while ((a_pbb = (outer == loop_at (scop, index))) | |
1172 | || nested_in (loop_at (scop, index), outer)) | |
1173 | { | |
1174 | if (a_pbb) | |
1175 | s = add_in_sequence (s, build_schedule_pbb (scop, index)); | |
1176 | else | |
1177 | s = add_in_sequence (s, build_schedule_loop (scop, index)); | |
1178 | ||
1179 | if (*index == max) | |
1180 | break; | |
1181 | } | |
1182 | ||
1183 | /* We reached the end of the OUTER loop: embed S in OUTER. */ | |
1184 | return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop), scop, | |
1185 | outer, index, context_loop); | |
1186 | } | |
1187 | ||
1188 | /* Build schedule for the full loop nest containing the pbb at INDEX. When | |
1189 | CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP | |
1190 | surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop | |
1191 | nest contained within CONTEXT_LOOP. */ | |
1192 | ||
1193 | static isl_schedule * | |
1194 | build_schedule_loop_nest (scop_p scop, int *index, loop_p context_loop) | |
1195 | { | |
1196 | gcc_assert (*index != (int) scop->pbbs.length ()); | |
1197 | ||
1198 | loop_p loop = loop_at (scop, index); | |
1199 | isl_schedule *s = build_schedule_loop (scop, index); | |
1200 | return embed_in_surrounding_loops (s, scop, loop, index, context_loop); | |
1201 | } | |
1202 | ||
1203 | /* Build the schedule of the SCOP. */ | |
1204 | ||
1205 | static bool | |
1206 | build_original_schedule (scop_p scop) | |
1207 | { | |
197d2f5b RB |
1208 | schedule_error = false; |
1209 | ||
adba512d AK |
1210 | int i = 0; |
1211 | int n = scop->pbbs.length (); | |
1212 | while (i < n) | |
1213 | { | |
1214 | poly_bb_p pbb = scop->pbbs[i]; | |
1215 | isl_schedule *s = NULL; | |
1216 | if (!loop_in_sese_p (pbb_loop (pbb), scop->scop_info->region)) | |
1217 | s = build_schedule_pbb (scop, &i); | |
1218 | else | |
1219 | s = build_schedule_loop_nest (scop, &i, NULL); | |
1220 | ||
1221 | scop->original_schedule = add_in_sequence (scop->original_schedule, s); | |
1222 | } | |
1223 | ||
197d2f5b RB |
1224 | if (schedule_error) |
1225 | { | |
1226 | if (dump_file) | |
1227 | fprintf (dump_file, "[sese-to-poly] failed to build " | |
1228 | "original schedule\n"); | |
1229 | return false; | |
1230 | } | |
1231 | ||
adba512d AK |
1232 | if (dump_file) |
1233 | { | |
1234 | fprintf (dump_file, "[sese-to-poly] original schedule:\n"); | |
1235 | print_isl_schedule (dump_file, scop->original_schedule); | |
1236 | } | |
1237 | if (!scop->original_schedule) | |
1238 | return false; | |
1239 | return true; | |
1240 | } | |
1241 | ||
2abae5f1 SP |
1242 | /* Builds the polyhedral representation for a SESE region. */ |
1243 | ||
36f40be0 | 1244 | bool |
2abae5f1 SP |
1245 | build_poly_scop (scop_p scop) |
1246 | { | |
871a0725 RB |
1247 | int old_err = isl_options_get_on_error (scop->isl_context); |
1248 | isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE); | |
1249 | ||
2abae5f1 | 1250 | build_scop_context (scop); |
36f40be0 | 1251 | |
d8d262cf AK |
1252 | unsigned i = 0; |
1253 | unsigned n = scop->pbbs.length (); | |
1254 | while (i < n) | |
1255 | i = build_iteration_domains (scop, scop->param_context, i, NULL); | |
1256 | ||
efa21390 | 1257 | build_scop_drs (scop); |
adba512d | 1258 | build_original_schedule (scop); |
871a0725 RB |
1259 | |
1260 | enum isl_error err = isl_ctx_last_error (scop->isl_context); | |
1261 | isl_ctx_reset_error (scop->isl_context); | |
1262 | isl_options_set_on_error (scop->isl_context, old_err); | |
1263 | if (err != isl_error_none) | |
1264 | dump_printf (MSG_MISSED_OPTIMIZATION, | |
1265 | "ISL error while building poly scop\n"); | |
1266 | ||
1267 | return err == isl_error_none; | |
2abae5f1 | 1268 | } |
9c358739 | 1269 | #endif /* HAVE_isl */ |