?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Proper skew transformation
[clay.git] / source / transformation.c
blob98593e8beda906cd9fde80402e3e7cbaa1e61ad0
1
2 /*--------------------------------------------------------------------+
3 | Clay |
4 |--------------------------------------------------------------------|
5 | transformation.c |
6 |--------------------------------------------------------------------|
7 | First version: 03/04/2012 |
8 +--------------------------------------------------------------------+
9
10 +--------------------------------------------------------------------------+
11 | / __)( ) /__\ ( \/ ) |
12 | ( (__ )(__ /(__)\ \ / Chunky Loop Alteration wizardrY |
13 | \___)(____)(__)(__)(__) |
14 +--------------------------------------------------------------------------+
15 | Copyright (C) 2012 University of Paris-Sud |
16 | |
17 | This library is free software; you can redistribute it and/or modify it |
18 | under the terms of the GNU Lesser General Public License as published by |
19 | the Free Software Foundation; either version 2.1 of the License, or |
20 | (at your option) any later version. |
21 | |
22 | This library is distributed in the hope that it will be useful but |
23 | WITHOUT ANY WARRANTY; without even the implied warranty of |
24 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser |
25 | General Public License for more details. |
26 | |
27 | You should have received a copy of the GNU Lesser General Public License |
28 | along with this software; if not, write to the Free Software Foundation, |
29 | Inc., 51 Franklin Street, Fifth Floor, |
30 | Boston, MA 02110-1301 USA |
31 | |
32 | Clay, the Chunky Loop Alteration wizardrY |
33 | Written by Joel Poudroux, joel.poudroux@u-psud.fr |
34 +--------------------------------------------------------------------------*/
35
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <string.h>
39
40 #include <osl/macros.h>
41 #include <osl/scop.h>
42 #include <osl/body.h>
43 #include <osl/strings.h>
44 #include <osl/util.h>
45 #include <osl/statement.h>
46 #include <osl/relation.h>
47 #include <osl/generic.h>
48 #include <osl/extensions/scatnames.h>
49 #include <osl/extensions/arrays.h>
50 #include <osl/extensions/extbody.h>
51
52 #include <clay/transformation.h>
53 #include <clay/array.h>
54 #include <clay/list.h>
55 #include <clay/macros.h>
56 #include <clay/options.h>
57 #include <clay/errors.h>
58 #include <clay/beta.h>
59 #include <clay/util.h>
60
61
62 /*****************************************************************************\
63 * Loop transformations *
64 `****************************************************************************/
65
66 /**
67 * clay_reorder function:
68 * Reorders the statements in the loop
69 * \param[in,out] scop
70 * \param[in] beta_loop Loop beta vector
71 * \param[in] order Array to reorder the statements
72 * \param[in] options
73 * \return Status
74 */
75 int clay_reorder(osl_scop_p scop,
76 clay_array_p beta_loop, clay_array_p neworder,
77 clay_options_p options) {
78 // Replace element in the nested beta-vectors with respect to the values in
79 // the neworder array.
80
81 osl_relation_p scattering;
82 osl_statement_p statement;
83 int precision;
84 const int column = beta_loop->size * 2; // relation_get_line adds 1 -> beta
85 int row;
86 int index;
87
88 // Ensure that beta-vectors are normalized since we use their elements as
89 // indices to neworder array.
90 clay_beta_normalize(scop);
91
92 statement = clay_beta_find(scop->statement, beta_loop);
93 if (!statement)
94 return CLAY_ERROR_BETA_NOT_FOUND;
95
96 precision = statement->scattering->precision;
97 while (statement != NULL) {
98 scattering = statement->scattering;
99 while (scattering != NULL) {
100 // Select all the parts of relation union that match current beta.
101 if (!clay_beta_check_relation(scattering, beta_loop)) {
102 scattering = scattering->next;
103 continue;
104 }
105 CLAY_BETA_IS_LOOP(beta_loop, scattering);
106
107 row = clay_util_relation_get_line(scattering, column);
108
109 // Get the beta value.
110 index = osl_int_get_si(precision,
111 scattering->m[row][scattering->nb_columns - 1]);
112
113 if (index >= neworder->size)
114 return CLAY_ERROR_REORDER_ARRAY_TOO_SMALL;
115
116 osl_int_set_si(precision,
117 &scattering->m[row][scattering->nb_columns - 1],
118 neworder->data[index]);
119 scattering = scattering->next;
120 }
121 statement = statement->next;
122 }
123
124 // Normalize again if asked (useful if the neworder was not normalized).
125 if (options && options->normalize)
126 clay_beta_normalize(scop);
127
128 return CLAY_SUCCESS;
129 }
130
131
132 /**
133 * clay_reverse function:
134 * Reverse the direction of the loop
135 * \param[in,out] scop
136 * \param[in] beta Beta vector
137 * \param[in] options
138 * \return Status
139 */
140 int clay_reverse(osl_scop_p scop, clay_array_p beta, unsigned int depth,
141 clay_options_p options) {
142 // Oppose the output_dims column at the `depth'th level.
143
144 if (beta->size == 0)
145 return CLAY_ERROR_BETA_EMPTY;
146 if (depth <= 0)
147 return CLAY_ERROR_DEPTH_OVERFLOW;
148
149 osl_relation_p scattering;
150 osl_statement_p statement = scop->statement;
151 int precision;
152 int column = depth*2 - 1; // iterator column
153 int i;
154
155 statement = clay_beta_find(statement, beta);
156 if (!statement)
157 return CLAY_ERROR_BETA_NOT_FOUND;
158
159 while (statement != NULL) {
160 scattering = statement->scattering;
161 while (scattering != NULL) {
162 precision = scattering->precision;
163 CLAY_BETA_CHECK_DEPTH(beta, depth, scattering);
164 if (clay_beta_check_relation(scattering, beta)) {
165 for (i = 0; i < scattering->nb_rows; i++) {
166 osl_int_oppose(precision,
167 &scattering->m[i][column + 1],
168 scattering->m[i][column + 1]);
169 }
170 }
171 scattering = scattering->next;
172 }
173 statement = statement->next;
174 }
175
176 return CLAY_SUCCESS;
177 }
178
179
180 /**
181 * clay_interchange function:
182 * On each statement which belongs to the `beta', the loops that match the
183 * `depth_1'th and the `depth_2' are interchanged
184 * /!\ If you want to interchange 2 loops, you must give the inner beta loop
185 * and not the outer !
186 * \param[in,out] scop
187 * \param[in] beta Beta vector (inner loop or statement)
188 * \param[in] depth_1 >= 1
189 * \param[in] depth_2 >= 1
190 * \param[in] pretty 1 or 0 : update the scatnames
191 * \param[in] options
192 * \return Status
193 */
194 int clay_interchange(osl_scop_p scop,
195 clay_array_p beta,
196 unsigned int depth_1, unsigned int depth_2,
197 int pretty,
198 clay_options_p options) {
199 // Swap the two output_dims columns.
200
201 if (beta->size == 0)
202 return CLAY_ERROR_BETA_EMPTY;
203 if (depth_1 <= 0 || depth_2 <= 0)
204 return CLAY_ERROR_DEPTH_OVERFLOW;
205
206 osl_statement_p statement = scop->statement;
207 osl_relation_p scattering;
208 int precision;
209 const int column_1 = depth_1*2 - 1; // iterator column
210 const int column_2 = depth_2*2 - 1;
211 int i;
212 osl_int_t **matrix;
213
214 statement = clay_beta_find(statement, beta);
215 if (!statement)
216 return CLAY_ERROR_BETA_NOT_FOUND;
217
218 scattering = statement->scattering;
219 while (scattering != NULL) {
220 if (scattering->nb_output_dims <= 1)
221 return CLAY_ERROR_DEPTH_OVERFLOW;
222 CLAY_BETA_CHECK_DEPTH(beta, depth_1, scattering);
223 CLAY_BETA_CHECK_DEPTH(beta, depth_2, scattering);
224 scattering = scattering->next;
225 }
226
227 // Swapping with itself doesn't affect the scattering.
228 if (depth_1 == depth_2)
229 return CLAY_SUCCESS;
230
231 precision = statement->scattering->precision;
232 while (statement != NULL) {
233 scattering = statement->scattering;
234 while (scattering != NULL) {
235 if (clay_beta_check_relation(scattering, beta)) {
236 // Swap the two columns.
237 matrix = scattering->m;
238 for (i = 0 ; i < scattering->nb_rows ; i++)
239 osl_int_swap(precision,
240 &matrix[i][column_1+1],
241 &matrix[i][column_2+1]);
242 }
243 scattering = scattering->next;
244 }
245 statement = statement->next;
246 }
247
248 // swap the two variables
249 if (pretty) {
250 osl_scatnames_p scat;
251 osl_strings_p names;
252 scat = osl_generic_lookup(scop->extension, OSL_URI_SCATNAMES);
253 names = scat->names;
254
255 int ii = 0;
256 for (ii = 0 ; names->string[ii] ; ii++)
257 ;
258
259 int c1 = depth_1 * 2 - 1;
260 int c2 = depth_2 * 2 - 1;
261
262 if (c1 < ii && c2 < ii) {
263 char *tmp = names->string[c1];
264 names->string[c1] = names->string[c2];
265 names->string[c2] = tmp;
266 }
267 }
268
269 return CLAY_SUCCESS;
270 }
271
272
273 /**
274 * clay_split function:
275 * Split the loop in two parts at the `depth'th level from the statement
276 * \param[in,out] scop
277 * \param[in] beta Beta vector
278 * \param[in] depth >= 1
279 * \param[in] options
280 * \return Status
281 */
282 int clay_split(osl_scop_p scop, clay_array_p beta, unsigned int depth,
283 clay_options_p options) {
284
285 /* Description:
286 * Add one on the beta at the `depth'th level.
287 */
288
289 if (beta->size == 0)
290 return CLAY_ERROR_BETA_EMPTY;
291 if (beta->size <= 1 || depth <= 0 || depth >= beta->size)
292 return CLAY_ERROR_DEPTH_OVERFLOW;
293
294 osl_statement_p statement = scop->statement;
295 statement = clay_beta_find(statement, beta);
296 if (!statement)
297 return CLAY_ERROR_BETA_NOT_FOUND;
298
299 clay_beta_shift_after(scop->statement, beta, depth);
300
301 if (options && options->normalize)
302 clay_beta_normalize(scop);
303
304 return CLAY_SUCCESS;
305 }
306
307
308 /**
309 * clay_fuse function:
310 * Fuse loop with the first loop after
311 * \param[in,out] scop
312 * \param[in] beta_loop Loop beta vector
313 * \param[in] options
314 * \return Status
315 */
316 int clay_fuse(osl_scop_p scop, clay_array_p beta_loop,
317 clay_options_p options) {
318
319 /* Description:
320 * Set the same beta (only at the level of the beta_loop) on the next loop.
321 */
322
323 if (beta_loop->size == 0)
324 return CLAY_ERROR_BETA_EMPTY;
325
326 osl_relation_p scattering;
327 osl_statement_p statement;
328 clay_array_p beta_max;
329 clay_array_p beta_next;
330 int precision;
331 const int depth = beta_loop->size;
332 const int column = beta_loop->size*2; // alpha column
333 int row;
334
335 statement = clay_beta_find(scop->statement, beta_loop);
336 if (!statement)
337 return CLAY_ERROR_BETA_NOT_FOUND;
338
339 scattering = statement->scattering;
340 while (scattering != NULL) {
341 if (clay_beta_check_relation(scattering, beta_loop)) {
342 CLAY_BETA_IS_LOOP(beta_loop, scattering);
343 }
344 scattering = scattering->next;
345 }
346
347 precision = statement->scattering->precision;
348
349 beta_max = clay_beta_max(statement, beta_loop);
350 beta_next = clay_beta_next_part(scop->statement, beta_loop);
351
352 if (beta_next != NULL) {
353 beta_next->size = depth;
354 statement = scop->statement;
355 while (statement != NULL) {
356 scattering = statement->scattering;
357 while (scattering != NULL) {
358 if (clay_beta_check_relation(scattering, beta_next)) {
359 if (column < scattering->nb_output_dims) {
360 // Set the loop level
361 row = clay_util_relation_get_line(scattering, column-2);
362 osl_int_set_si(precision,
363 &scattering->m[row][scattering->nb_columns-1],
364 beta_loop->data[depth-1]);
365
366 // Reorder the statement
367 row = clay_util_relation_get_line(scattering, column);
368 osl_int_add_si(precision,
369 &scattering->m[row][scattering->nb_columns-1],
370 scattering->m[row][scattering->nb_columns-1],
371 beta_max->data[depth]+1);
372 }
373 }
374 scattering = scattering->next;
375 }
376 statement = statement->next;
377 }
378 clay_array_free(beta_next);
379 }
380
381 clay_array_free(beta_max);
382
383 if (options && options->normalize)
384 clay_beta_normalize(scop);
385
386 return CLAY_SUCCESS;
387 }
388
389
390 /**
391 * Skew the loop, i.e. add an outer iterator of the loop nest multiplied by the
392 * coefficient to the current loop iterator. Use the beta-prefix length to
393 * identify the "target" iteartor, use #depth to identify the outer loop
394 * ("source") iterator.
395 * (i, j) -> (i, j+i*coeff).
396 * Skew applies only to loops by definition. To perform the skewing
397 * transformation for a statement, split it and then do the skewing, or call
398 * shift directly.
399 * \param[in,out] scop
400 * \param[in] beta Beta-prefix that identifies the loop to skew
401 * \param[in] depth Depth of the "source" loop iterator (between 1 and length of beta-prefix)
402 * \param[in] coeff Coefficient for the "source" iterator.
403 * \param[in] options Clay options
404 * \return Status
405 */
406 int clay_skew(osl_scop_p scop,
407 clay_array_p beta, unsigned int depth, unsigned int coeff,
408 clay_options_p options) {
409
410 /* Description:
411 * This is a special case of shifting, where params and constant
412 * are equal to zero.
413 *
414 * Call clay_shift with the same beta, depth = beta_size and a vector set up
415 * so that it corresponds to 1*i + coeff*j shifting, i.e. it contains the
416 * value coeff at depth-s index and 1 at the end, all the other elements
417 * being zero.
418 *
419 * Individual statements cannot be skewed because we do not have information.
420 * The length of the beta-prefix is used to indentify the loop to skew, which
421 * would require an addiitonal parameter in case of beta-vector for
422 * statement.
423 */
424
425 if (beta->size == 0)
426 return CLAY_ERROR_BETA_EMPTY;
427 if (depth <= 0 || depth >= beta->size)
428 return CLAY_ERROR_DEPTH_OVERFLOW;
429 if (coeff == 0)
430 return CLAY_ERROR_WRONG_COEFF;
431
432 clay_list_p vector;
433 int i, ret;
434 osl_statement_p statement;
435 osl_relation_p scattering;
436
437 // Check if beta matches only loops.
438 statement = clay_beta_find(scop->statement, beta);
439 while (statement != NULL) {
440 for (scattering = statement->scattering;
441 scattering != NULL;
442 scattering = scattering->next) {
443 if (!clay_beta_check_relation(scattering, beta))
444 continue;
445 CLAY_BETA_IS_LOOP(beta, scattering);
446 }
447 statement = statement->next;
448 }
449
450 // create the vector
451 vector = clay_list_malloc();
452
453 // empty arrays
454 clay_list_add(vector, clay_array_malloc());
455 clay_list_add(vector, clay_array_malloc());
456 clay_list_add(vector, clay_array_malloc());
457
458 // set output dims
459 for (i = 0 ; i < depth-1 ; i++)
460 clay_array_add(vector->data[0], 0);
461 clay_array_add(vector->data[0], coeff);
462 for (i = depth + 1; i < beta->size; i++)
463 clay_array_add(vector->data[0], 0);
464 clay_array_add(vector->data[0], 1);
465
466 ret = clay_shift(scop, beta, beta->size, vector, options);
467 clay_list_free(vector);
468
469 return ret;
470 }
471
472
473 /**
474 * clay_iss function:
475 * Split the loop (or statement) depending of an inequation.
476 * Warning: in the output part, don't put the alpha columns
477 * example: if the output dims are : 0 i 0 j 0, just do Ni, Nj
478 * \param[in,out] scop
479 * \param[in] beta_loop Beta loop
480 * \param[in] inequation array {(([output, ...],) [param, ...],) [const]}
481 * \param[out] beta_max If NULL, the beta_max will not be returned.
482 * If function terminated successfully, the last
483 * beta which has the prefix beta_loop, NULL
484 * otherwise
485 * \param[in] options
486 * \return Status
487 */
488 int clay_iss(osl_scop_p scop,
489 clay_array_p beta_loop, clay_list_p inequ,
490 clay_array_p *ret_beta_max,
491 clay_options_p options) {
492
493 /* Description:
494 * Add the inequality to each scattering relation union that corresponds to
495 * the given beta.
496 */
497
498 if (beta_loop->size == 0)
499 return CLAY_ERROR_BETA_EMPTY;
500 if (inequ->size > 3)
501 return CLAY_ERROR_INEQU;
502
503 osl_statement_p statement;
504 osl_relation_p scattering;
505 clay_array_p beta_max;
506 int nb_output_dims, nb_parameters;
507 int order; // new loop order for the clones
508
509 // search a statement
510 statement = clay_beta_find(scop->statement, beta_loop);
511 if (!statement)
512 return CLAY_ERROR_BETA_NOT_FOUND;
513 if (statement->scattering->nb_input_dims == 0)
514 return CLAY_ERROR_BETA_NOT_IN_A_LOOP;
515
516 // decompose the inequation
517 nb_parameters = scop->context->nb_parameters;
518 nb_output_dims = statement->scattering->nb_output_dims;
519
520 if (inequ->size == 3) {
521 // pad zeros
522 clay_util_array_output_dims_pad_zero(inequ->data[0]);
523
524 if (inequ->data[0]->size > nb_output_dims ||
525 inequ->data[1]->size > nb_parameters ||
526 inequ->data[2]->size > 1)
527 return CLAY_ERROR_INEQU;
528
529 } else if (inequ->size == 2) {
530 if (inequ->data[0]->size > nb_parameters ||
531 inequ->data[1]->size > 1)
532 return CLAY_ERROR_INEQU;
533
534 } else if (inequ->size == 1) {
535 if (inequ->data[0]->size > 1)
536 return CLAY_ERROR_INEQU;
537 }
538
539 // set the beginning of 'order'
540 beta_max = clay_beta_max(statement, beta_loop);
541 order = beta_max->data[beta_loop->size] + 1; // beta_loop->size is in range
542 // since loop contains statements
543 if (ret_beta_max != NULL) {
544 *ret_beta_max = beta_max;
545 }
546
547 // ensure ret_beta_max is set up before returning success
548 if (inequ->size == 0) {
549 clay_array_free(beta_max);
550 return CLAY_SUCCESS;
551 }
552
553 // insert the inequation on each statements
554 while (statement != NULL) {
555 if (clay_beta_check(statement, beta_loop)) {
556
557 osl_relation_p last = statement->scattering;
558 while (last->next != NULL) {
559 last = last->next;
560 }
561 last->next = osl_relation_clone(statement->scattering);
562 last = last->next;
563 scattering = statement->scattering;
564 while (last != NULL) {
565 CLAY_BETA_IS_LOOP(beta_loop, scattering);
566 clay_util_relation_insert_inequation(scattering, inequ);
567 clay_util_relation_insert_inequation(last, inequ);
568 clay_util_relation_negate_row(last, last->nb_rows - 1);
569
570 clay_array_p new_beta = clay_array_clone(beta_max);
571 new_beta->data[beta_loop->size]++; //# ?= order
572 clay_util_scattering_update_beta(scattering, new_beta);
573 clay_array_free(new_beta);
574
575 last = last->next;
576 scattering = scattering->next;
577 }
578 }
579 statement = statement->next;
580 }
581
582 if (options && options->normalize)
583 clay_beta_normalize(scop);
584
585 return CLAY_SUCCESS;
586 }
587
588
589 /**
590 * clay_stripmine function:
591 * Decompose a single loop into two nested loop
592 * \param[in,out] scop
593 * \param[in] beta Beta vector (loop or statement)
594 * \param[in] size Block size of the inner loop
595 * \param[in] pretty If true, clay will keep the variables name
596 * \param[in] options
597 * \return Status
598 */
599 int clay_stripmine(osl_scop_p scop, clay_array_p beta,
600 unsigned int depth, unsigned int size,
601 int pretty, clay_options_p options) {
602
603 /* Description:
604 * Add two inequality for the stripmining.
605 * The new dependance with the loop is done on an output_dim.
606 * If pretty is true, we add for each statements (not only the beta) two
607 * output_dims (one for the iterator and one for the 2*n+1).
608 */
609
610 if (beta->size == 0)
611 return CLAY_ERROR_BETA_EMPTY;
612 if (size <= 0)
613 return CLAY_ERROR_WRONG_BLOCK_SIZE;
614 if (depth <= 0)
615 return CLAY_ERROR_DEPTH_OVERFLOW;
616
617 osl_relation_p scattering;
618 osl_statement_p statement = scop->statement;
619 osl_scatnames_p scat;
620 osl_strings_p names;
621 int column = (depth-1)*2; // alpha column
622 int precision;
623 int row, row_next;
624 int i;
625 int nb_strings;
626 char buffer[OSL_MAX_STRING];
627 char *new_var_iter;
628 char *new_var_beta;
629
630 statement = clay_beta_find(statement, beta);
631 if (!statement)
632 return CLAY_ERROR_BETA_NOT_FOUND;
633 if (statement->scattering->nb_output_dims < 3)
634 return CLAY_ERROR_BETA_NOT_IN_A_LOOP;
635
636 precision = statement->scattering->precision;
637 if (pretty)
638 statement = scop->statement; // TODO optimization...
639
640 while (statement != NULL) {
641 scattering = statement->scattering;
642 while (scattering != NULL) {
643 CLAY_BETA_CHECK_DEPTH(beta, depth, scattering);
644 if (clay_beta_check_relation(scattering, beta)) {
645
646 // set the strip mine
647 row = clay_util_relation_get_line(scattering, column);
648
649 osl_relation_insert_blank_column(scattering, column+1);
650 osl_relation_insert_blank_column(scattering, column+1);
651
652 osl_relation_insert_blank_row(scattering, column);
653 osl_relation_insert_blank_row(scattering, column);
654 osl_relation_insert_blank_row(scattering, column);
655
656 // stripmine
657 osl_int_set_si(precision, &scattering->m[row+0][column+1], -1);
658 osl_int_set_si(precision, &scattering->m[row+1][column+2], -size);
659 osl_int_set_si(precision, &scattering->m[row+2][column+2], size);
660 osl_int_set_si(precision,
661 &scattering->m[row+2][scattering->nb_columns-1],
662 size-1);
663
664 // inequality
665 osl_int_set_si(precision, &scattering->m[row+1][0], 1);
666 osl_int_set_si(precision, &scattering->m[row+2][0], 1);
667
668 // iterator dependance
669 osl_int_set_si(precision, &scattering->m[row+1][column+4], 1);
670 osl_int_set_si(precision, &scattering->m[row+2][column+4], -1);
671
672 scattering->nb_output_dims += 2;
673
674 // reorder
675 row_next = clay_util_relation_get_line(scattering, column+2);
676 osl_int_assign(precision,
677 &scattering->m[row][scattering->nb_columns-1],
678 scattering->m[row_next][scattering->nb_columns-1]);
679
680 osl_int_set_si(precision,
681 &scattering->m[row_next][scattering->nb_columns-1],
682 0);
683
684 } else if (pretty && column < scattering->nb_output_dims) {
685 // add 2 empty dimensions
686 row = clay_util_relation_get_line(scattering, column);
687
688 osl_relation_insert_blank_column(scattering, column+1);
689 osl_relation_insert_blank_column(scattering, column+1);
690
691 osl_relation_insert_blank_row(scattering, column);
692 osl_relation_insert_blank_row(scattering, column);
693
694 // -Identity
695 osl_int_set_si(precision, &scattering->m[row][column+1], -1);
696 osl_int_set_si(precision, &scattering->m[row+1][column+2], -1);
697
698 scattering->nb_output_dims += 2;
699
700 // reorder
701 row_next = clay_util_relation_get_line(scattering, column+2);
702 osl_int_assign(precision,
703 &scattering->m[row][scattering->nb_columns-1],
704 scattering->m[row_next][scattering->nb_columns-1]);
705
706 osl_int_set_si(precision,
707 &scattering->m[row_next][scattering->nb_columns-1],
708 0);
709 }
710
711 scattering = scattering->next;
712 }
713 statement = statement->next;
714 }
715
716 // get the list of scatnames
717 scat = osl_generic_lookup(scop->extension, OSL_URI_SCATNAMES);
718 names = scat->names;
719
720 // generate iterator variable name
721 i = 0;
722 do {
723 sprintf(buffer, "__%s%s%d", names->string[column+1],
724 names->string[column+1], i);
725 i++;
726 } while (clay_util_scatnames_exists(scat, buffer));
727 new_var_iter = strdup(buffer);
728
729 // generate beta variable name
730 i = 0;
731 do {
732 sprintf(buffer, "__b%d", i);
733 i++;
734 } while (clay_util_scatnames_exists(scat, buffer));
735 new_var_beta = strdup(buffer);
736
737 // insert the two variables
738 nb_strings = osl_strings_size(names) + 2;
739 osl_strings_p newnames = osl_strings_malloc();
740 CLAY_malloc(newnames->string, char**, sizeof(char**) * (nb_strings + 1));
741
742 for (i = 0 ; i < column ; i++)
743 newnames->string[i] = names->string[i];
744
745 newnames->string[i] = new_var_beta;
746 newnames->string[i+1] = new_var_iter;
747
748 for (i = i+2 ; i < nb_strings ; i++)
749 newnames->string[i] = names->string[i-2];
750
751 newnames->string[i] = NULL; // end of the list
752
753 // replace the scatnames
754 free(names->string);
755 free(names);
756 scat->names = newnames;
757
758 osl_scop_print(stderr, scop);
759 if (options && options->normalize)
760 clay_beta_normalize(scop);
761
762 return CLAY_SUCCESS;
763 }
764
765
766 /** clay_unroll function: Unroll a loop \param[in,out] scop \param[in]
767 * beta_loop Loop beta vector \param[in] factor > 0 \param[in]
768 * setepilog if true the epilog will be added \param[in] options \return
769 * Status
770 */
771 int clay_unroll(osl_scop_p scop, clay_array_p beta_loop, unsigned int factor,
772 int setepilog, clay_options_p options) {
773
774 /* Description:
775 * Clone statements in the beta_loop, and recreate the body.
776 * Generate an epilog where the lower bound was removed.
777 */
778
779 if (beta_loop->size == 0)
780 return CLAY_ERROR_BETA_EMPTY;
781 if (factor < 1)
782 return CLAY_ERROR_WRONG_FACTOR;
783 if (factor == 1)
784 return CLAY_SUCCESS;
785
786 osl_relation_p scattering;
787 osl_relation_p domain;
788 osl_relation_p epilog_domain = NULL;
789 osl_statement_p statement;
790 osl_statement_p newstatement;
791 osl_statement_p original_stmt;
792 osl_statement_p epilog_stmt;
793 clay_array_p beta_max;
794 int column = beta_loop->size*2;
795 int precision;
796 int row;
797 int nb_stmts;
798 int i;
799 int max; // last value of beta_max
800 int order;
801 int order_epilog = 0; // order juste after the beta_loop
802 int current_stmt = 0; // counter of statements
803 int last_level = -1;
804 int current_level;
805
806 osl_body_p body = NULL;
807 osl_extbody_p ext_body = NULL;
808 osl_body_p newbody = NULL;
809 osl_extbody_p newextbody = NULL;
810 osl_body_p tmpbody = NULL;
811 osl_generic_p gen = NULL;
812 char *expression;
813 char **iterator;
814 char *substitued;
815 char *newexpression;
816 char *replacement;
817 char substitution[] = "@0@";
818
819 int iterator_index = beta_loop->size-1;
820 int iterator_size;
821
822 int is_extbody = 0;
823
824 statement = clay_beta_find(scop->statement, beta_loop);
825 if (!statement)
826 return CLAY_ERROR_BETA_NOT_FOUND;
827
828 precision = statement->scattering->precision;
829
830 // alloc an array of string, wich will contain the current iterator and NULL
831 // used for osl_util_identifier_substitution with only one variable
832 CLAY_malloc(iterator, char**, sizeof(char*)*2);
833 iterator[1] = NULL;
834
835 // infos used to reorder cloned statements
836 nb_stmts = clay_beta_nb_parts(statement, beta_loop);
837 beta_max = clay_beta_max(statement, beta_loop);
838 max = beta_max->data[beta_max->size-1];
839 clay_array_free(beta_max);
840
841 if (setepilog) {
842 // shift to let the place for the epilog loop
843 clay_beta_shift_after(scop->statement, beta_loop, beta_loop->size);
844 order_epilog = beta_loop->data[beta_loop->size-1] + 1;
845 }
846
847 while (statement != NULL) {
848 scattering = statement->scattering;
849
850 if (clay_beta_check(statement, beta_loop)) {
851
852 // create the body with symbols for the substitution
853 original_stmt = statement;
854
855 ext_body = osl_generic_lookup(statement->extension,
856 OSL_URI_EXTBODY);
857 if (ext_body) {
858 body = ext_body->body;
859 is_extbody = 1;
860 } else {
861 body = (osl_body_p) osl_generic_lookup(statement->extension,
862 OSL_URI_BODY);
863 }
864 if (body == NULL)
865 CLAY_error("Missing statement body\n");
866
867 expression = body->expression->string[0];
868 iterator[0] = (char*) body->iterators->string[iterator_index];
869 iterator_size = strlen(iterator[0]);
870 substitued = osl_util_identifier_substitution(expression, iterator);
871
872 CLAY_malloc(replacement, char*, 1 + iterator_size + 1 + 16 + 1 + 1);
873
874 if (setepilog) {
875 // Clone the statment with only those parts of scattering relation
876 // union, that match the given beta, and modify these parts
877 // accordingly.
878 epilog_stmt = osl_statement_malloc();
879 epilog_stmt->domain = osl_relation_clone(original_stmt->domain);
880 epilog_stmt->access = osl_relation_list_clone(original_stmt->access);
881 epilog_stmt->extension = osl_generic_clone(original_stmt->extension);
882 epilog_stmt->scattering = NULL;
883 epilog_stmt->next = NULL;
884 osl_relation_p scat = original_stmt->scattering;
885 osl_relation_p ptr = NULL;
886 while (scat != NULL) {
887 if (clay_beta_check_relation(scat, beta_loop)) {
888 CLAY_BETA_IS_LOOP(beta_loop, scat);
889 if (ptr == NULL) {
890 epilog_stmt->scattering = osl_relation_nclone(scat, 1);
891 ptr = epilog_stmt->scattering;
892 } else {
893 ptr->next = osl_relation_nclone(scat, 1);
894 ptr = ptr->next;
895 }
896
897 row = clay_util_relation_get_line(scat, column - 2);
898 osl_int_set_si(precision,
899 &ptr->m[row][ptr->nb_columns-1],
900 order_epilog);
901
902 //# AZ: fixing up post-iss changes to scattering union, that would be
903 //translated into loop boundary changes, namely removing presumably
904 //lower bound (FIXME!) conditions on the alpha dimension corresponding
905 //to the unrolled iterator. Other possible solution: take the lower
906 //bound from unrolled statements, add +1 and transformed to the lower
907 //bound for epilog.
908 osl_relation_print(stderr, ptr);
909 for (i = 0; i < ptr->nb_rows; i++) {
910 if (osl_int_pos(precision, ptr->m[i][(iterator_index+1)*2])) {
911 osl_int_set_si(precision, &ptr->m[i][(iterator_index+1)*2], 0);
912 }
913 int j, to_remove = 1;
914 for (j = 0; j < ptr->nb_output_dims; j++) {
915 if (!osl_int_zero(precision, ptr->m[i][j+1])) {
916 to_remove = 0;
917 break;
918 }
919 }
920 if (to_remove) {
921 osl_relation_remove_row(ptr, i);
922 i--;
923 }
924 }
925 }
926 scat = scat->next;
927 }
928
929 // the order is not important in the statements list
930 epilog_stmt->next = statement->next;
931 statement->next = epilog_stmt;
932 statement = epilog_stmt;
933 }
934
935 // modify the matrix domain
936 domain = original_stmt->domain;
937
938 if (setepilog) {
939 epilog_domain = epilog_stmt->domain;
940 }
941
942 while (domain != NULL) {
943
944 for (i = domain->nb_rows-1 ; i >= 0 ; i--) {
945 if (!osl_int_zero(precision, domain->m[i][0])) {
946
947 // remove the lower bound on the epilog statement
948 if(setepilog &&
949 osl_int_pos(precision, domain->m[i][iterator_index+1])) {
950 osl_relation_remove_row(epilog_domain, i);
951 }
952 // remove the upper bound on the original statement
953 if (osl_int_neg(precision, domain->m[i][iterator_index+1])) {
954 osl_int_add_si(precision,
955 &domain->m[i][domain->nb_columns-1],
956 domain->m[i][domain->nb_columns-1],
957 -factor);
958 }
959 }
960 }
961
962 // Don't add local dimension to the domain since it may affect other
963 // parts of the statement scattered with different betas.
964
965 domain = domain->next;
966
967 if (setepilog)
968 epilog_domain = epilog_domain->next;
969 }
970
971 // clone factor-1 times the original statement
972
973 // FIXME: here scattering was pointing to the scattering of epilog (probably bug)
974 // FIXME: I don't see much sense in this magic: it sets current_stmt to 1
975 // (instead of 0) unless the last value of the beta-vector for epilog (if
976 // requested) or original statement was -1. Leave it as is.
977 row = clay_util_relation_get_line(original_stmt->scattering, column);
978 current_level = osl_int_get_si(scattering->precision,
979 scattering->m[row][scattering->nb_columns-1]);
980 if (last_level != current_level) {
981 current_stmt++;
982 last_level = current_level;
983 }
984
985 // Update those scattering relation union
986 scattering = original_stmt->scattering;
987 while (scattering != NULL) {
988 if (clay_beta_check_relation(scattering, beta_loop)) {
989 // Insert local dimension.
990 osl_relation_insert_blank_column(scattering, scattering->nb_output_dims + scattering->nb_input_dims + 1);
991 (scattering->nb_local_dims)++;
992 osl_relation_insert_blank_row(scattering, scattering->nb_rows);
993 osl_int_set_si(scattering->precision,
994 &scattering->m[scattering->nb_rows - 1][(iterator_index+1)*2],
995 1);
996 osl_int_set_si(scattering->precision,
997 &scattering->m[scattering->nb_rows - 1][scattering->nb_output_dims + scattering->nb_input_dims + 1],
998 -factor);
999 }
1000 scattering = scattering->next;
1001 }
1002
1003 for (i = 0 ; i < factor-1 ; i++) {
1004 // Clone the expression with only matching parts.
1005 newstatement = osl_statement_malloc();
1006 newstatement->domain = osl_relation_clone(original_stmt->domain);
1007 newstatement->access = osl_relation_list_clone(original_stmt->access);
1008 newstatement->extension = osl_generic_clone(original_stmt->extension);
1009 newstatement->next = NULL;
1010 newstatement->scattering = NULL;
1011 osl_relation_p ptr = NULL;
1012 osl_relation_p scat = original_stmt->scattering;
1013 while (scat != NULL) {
1014 if (clay_beta_check_relation(scat, beta_loop)) {
1015 if (ptr == NULL) {
1016 newstatement->scattering = osl_relation_nclone(scat, 1);
1017 ptr = newstatement->scattering;
1018 } else {
1019 ptr->next = osl_relation_nclone(scat, 1);
1020 ptr = ptr->next;
1021 }
1022 }
1023 scat = scat->next;
1024 }
1025
1026 scattering = newstatement->scattering;
1027 // reorder
1028 while (scattering != NULL) {
1029 order = current_stmt + max + nb_stmts*i;
1030 osl_int_set_si(precision,
1031 &scattering->m[row][scattering->nb_columns-1],
1032 order);
1033 scattering = scattering->next;
1034 }
1035
1036 // update the body
1037 sprintf(replacement, "(%s+%d)", iterator[0], i+1);
1038 newexpression = clay_util_string_replace(substitution, replacement,
1039 substitued);
1040
1041 if (is_extbody) {
1042 newextbody = osl_generic_lookup(newstatement->extension,
1043 OSL_URI_EXTBODY);
1044 newbody = newextbody->body;
1045 }
1046 else {
1047 newbody = osl_generic_lookup(newstatement->extension, OSL_URI_BODY);
1048 }
1049
1050 free(newbody->expression->string[0]);
1051 newbody->expression->string[0] = newexpression;
1052
1053 // synchronize extbody and body (if both are different)
1054 if (is_extbody) {
1055 tmpbody = osl_generic_lookup(newstatement->extension, OSL_URI_BODY);
1056 if (tmpbody) {
1057 osl_generic_remove(&newstatement->extension, OSL_URI_BODY);
1058 tmpbody = osl_body_clone(newbody);
1059 gen = osl_generic_shell(tmpbody, osl_body_interface());
1060 osl_generic_add(&newstatement->extension, gen);
1061 }
1062 }
1063
1064 // the order is not important in the statements list
1065 newstatement->next = statement->next;
1066 statement->next = newstatement;
1067 statement = newstatement;
1068 }
1069 free(substitued);
1070 free(replacement);
1071 }
1072 statement = statement->next;
1073 }
1074 free(iterator);
1075
1076 if (options && options->normalize)
1077 clay_beta_normalize(scop);
1078
1079 return CLAY_SUCCESS;
1080 }
1081
1082
1083 /**
1084 * clay_tile function:
1085 * Apply a stripmine then an interchange.
1086 * The stripmine is at the `depth'th level. Next interchange the level `depth'
1087 * and `depth_outer'
1088 * \param[in,out] scop
1089 * \param[in] beta Beta vector
1090 * \param[in] depth >=1
1091 * \param[in] size >=1
1092 * \param[in] depth_outer >=1
1093 * \param[in] pretty See stripmine
1094 * \param[in] options
1095 * \return Status
1096 */
1097 int clay_tile(osl_scop_p scop,
1098 clay_array_p beta, unsigned int depth, unsigned int depth_outer,
1099 unsigned int size, int pretty, clay_options_p options) {
1100
1101 /* Description:
1102 * stripmine + interchange
1103 */
1104
1105 if (beta->size == 0)
1106 return CLAY_ERROR_BETA_EMPTY;
1107 if (size <= 0)
1108 return CLAY_ERROR_WRONG_BLOCK_SIZE;
1109 if (depth <= 0 || depth_outer <= 0)
1110 return CLAY_ERROR_DEPTH_OVERFLOW;
1111 if (depth_outer > depth)
1112 return CLAY_ERROR_DEPTH_OUTER;
1113
1114 int ret;
1115 ret = clay_stripmine(scop, beta, depth, size, pretty, options);
1116
1117 if (ret == CLAY_SUCCESS) {
1118 ret = clay_interchange(scop, beta, depth, depth_outer, pretty, options);
1119 }
1120
1121 return ret;
1122 }
1123
1124
1125 /**
1126 * clay_shift function:
1127 * Shift the iteration domain
1128 * Warning: in the output part, don't put the alpha columns
1129 * example: if the output dims are : 0 i 0 j 0, just do Ni, Nj
1130 * \param[in,out] scop
1131 * \param[in] beta Beta vector (loop or statement)
1132 * \param[in] depth >=1
1133 * \param[in] vector {(([output, ...],) [param, ...],) [const]}
1134 * \param[in] options
1135 * \return Status
1136 */
1137 int clay_shift(osl_scop_p scop,
1138 clay_array_p beta, unsigned int depth, clay_list_p vector,
1139 clay_options_p options) {
1140
1141 /* Description:
1142 * Add a vector on each statements.
1143 */
1144
1145 if (beta->size == 0)
1146 return CLAY_ERROR_BETA_EMPTY;
1147 if (vector->size == 0)
1148 return CLAY_ERROR_VECTOR_EMPTY;
1149 if (depth <= 0)
1150 return CLAY_ERROR_DEPTH_OVERFLOW;
1151 if (vector->size > 3)
1152 return CLAY_ERROR_VECTOR;
1153 if (vector->size == 0)
1154 return CLAY_SUCCESS;
1155
1156 osl_statement_p statement;
1157 osl_relation_p scattering;
1158 const int column = depth*2 - 1; // iterator column
1159 int nb_parameters, nb_output_dims;
1160
1161 statement = clay_beta_find(scop->statement, beta);
1162 if (!statement)
1163 return CLAY_ERROR_BETA_NOT_FOUND;
1164
1165 // decompose the vector
1166 nb_parameters = scop->context->nb_parameters;
1167 nb_output_dims = statement->scattering->nb_output_dims;
1168
1169 if (vector->size == 3) {
1170 // pad zeros
1171 clay_util_array_output_dims_pad_zero(vector->data[0]);
1172
1173 if (vector->data[0]->size > nb_output_dims ||
1174 vector->data[1]->size > nb_parameters ||
1175 vector->data[2]->size > 1)
1176 return CLAY_ERROR_VECTOR;
1177
1178 } else if (vector->size == 2) {
1179 if (vector->data[0]->size > nb_parameters ||
1180 vector->data[1]->size > 1)
1181 return CLAY_ERROR_VECTOR;
1182
1183 } else if (vector->size == 1) {
1184 if (vector->data[0]->size > 1)
1185 return CLAY_ERROR_VECTOR;
1186 }
1187
1188 // add the vector for each statements
1189 while (statement != NULL) {
1190 scattering = statement->scattering;
1191 while (scattering != NULL) {
1192 if (clay_beta_check_relation(scattering, beta)) {
1193 CLAY_BETA_CHECK_DEPTH(beta, depth, scattering);
1194 if (scattering->nb_input_dims == 0) {
1195 return CLAY_ERROR_BETA_NOT_IN_A_LOOP;
1196 }
1197
1198 clay_util_relation_set_vector(scattering, vector, column);
1199 }
1200 scattering = scattering->next;
1201 }
1202 statement = statement->next;
1203 }
1204
1205 if (options && options->normalize)
1206 clay_beta_normalize(scop);
1207
1208 return CLAY_SUCCESS;
1209 }
1210
1211
1212 /**
1213 * clay_peel function:
1214 * Removes the first or last iteration of the loop into separate code.
1215 * This is equivalent to an iss (without output dims) and a spliting
1216 * \param[in,out] scop
1217 * \param[in] beta_loop Loop beta vector
1218 * \param[in] peeling list { ([param, ...],) [const] }
1219 * \param[in] options
1220 * \return Status
1221 */
1222 int clay_peel(osl_scop_p scop,
1223 clay_array_p beta_loop, clay_list_p peeling,
1224 clay_options_p options) {
1225
1226 if (beta_loop->size == 0)
1227 return CLAY_ERROR_BETA_EMPTY;
1228 if (peeling->size >= 3)
1229 return CLAY_ERROR_INEQU;
1230 if (peeling->size == 0)
1231 return CLAY_SUCCESS;
1232
1233 clay_array_p arr_dims, beta_max;
1234 clay_list_p new_peeling;
1235 int i, ret;
1236
1237 // create output dims
1238 arr_dims = clay_array_malloc();
1239 for (i = 0 ; i < beta_loop->size-1 ; i++)
1240 clay_array_add(arr_dims, 0);
1241 clay_array_add(arr_dims, 1);
1242
1243 // create new peeling list
1244 new_peeling = clay_list_malloc();
1245 clay_list_add(new_peeling, arr_dims);
1246 if (peeling->size == 2) {
1247 clay_list_add(new_peeling, peeling->data[0]);
1248 clay_list_add(new_peeling, peeling->data[1]);
1249 } else {
1250 clay_list_add(new_peeling, clay_array_malloc()); // empty params
1251 clay_list_add(new_peeling, peeling->data[0]);
1252 }
1253
1254 // index-set spliting
1255 ret = clay_iss(scop, beta_loop, new_peeling, &beta_max, options);
1256
1257 // we don't free ALL with clay_list_free, because there are arrays in
1258 // common with `peeling'
1259 clay_array_free(arr_dims);
1260 if (peeling->size == 1)
1261 clay_array_free(new_peeling->data[1]);
1262 free(new_peeling->data);
1263 free(new_peeling);
1264
1265 if (ret == CLAY_SUCCESS) {
1266 // see clay_split
1267 clay_beta_shift_after(scop->statement, beta_max,
1268 beta_loop->size);
1269 clay_array_free(beta_max);
1270 }
1271
1272 if (options && options->normalize)
1273 clay_beta_normalize(scop);
1274
1275 return ret;
1276 }
1277
1278
1279 /**
1280 * clay_context function:
1281 * Add a line to the context
1282 * \param[in,out] scop
1283 * \param[in] vector [param1, param2, ..., 1]
1284 * \param[in] options
1285 * \return Status
1286 */
1287 int clay_context(osl_scop_p scop, clay_array_p vector,
1288 clay_options_p options) {
1289
1290 /* Description:
1291 * Add a new line in the context matrix.
1292 */
1293
1294 if (vector->size < 2)
1295 return CLAY_ERROR_VECTOR;
1296 if (scop->context->nb_parameters != vector->size-2)
1297 return CLAY_ERROR_VECTOR;
1298
1299 osl_relation_p context;
1300 int row;
1301 int i, j;
1302 int precision;
1303
1304 context = scop->context;
1305 precision = context->precision;
1306 row = context->nb_rows;
1307 osl_relation_insert_blank_row(context, row);
1308
1309 osl_int_set_si(precision,
1310 &context->m[row][0],
1311 vector->data[0]);
1312
1313 j = 1 + context->nb_output_dims + context->nb_input_dims +
1314 context->nb_local_dims;
1315 for (i = 1 ; i < vector->size ; i++) {
1316 osl_int_set_si(precision,
1317 &context->m[row][j],
1318 vector->data[i]);
1319 j++;
1320 }
1321
1322 return CLAY_SUCCESS;
1323 }
1324
1325
1326 static int clay_dimreorder_aux(osl_relation_list_p access,
1327 void *args) {
1328 clay_array_p neworder = args;
1329 osl_relation_p a = access->elt;
1330
1331 if (a->nb_output_dims-1 != neworder->size) {
1332 fprintf(stderr, "[Clay] Warning: can't reorder dims on this statement: ");
1333 return CLAY_ERROR_REORDER_ARRAY_SIZE;
1334 }
1335
1336 osl_relation_p tmp = osl_relation_nclone(a, 1);
1337 int i, j;
1338
1339 for (i = 0 ; i < neworder->size ; i++) {
1340 if (neworder->data[i] < 0 ||
1341 neworder->data[i] >= a->nb_output_dims-1)
1342 return CLAY_ERROR_REORDER_OVERFLOW_VALUE;
1343
1344 if (i+2 != neworder->data[i]+2)
1345 for (j = 0 ; j < a->nb_rows ; j++)
1346 osl_int_assign(a->precision,
1347 &tmp->m[j][i+2],
1348 a->m[j][neworder->data[i]+2]);
1349 }
1350
1351 osl_relation_free(a);
1352 access->elt = tmp;
1353
1354 return CLAY_SUCCESS;
1355 }
1356
1357
1358 /**
1359 * clay_dimreorder function:
1360 * Reorder the dimensions of access_ident
1361 * \param[in,out] scop
1362 * \param[in] beta
1363 * \param[in] access_ident ident of the access array
1364 * \param[in] neworder reorder the dims
1365 * \param[in] options
1366 * \return Status
1367 */
1368 int clay_dimreorder(osl_scop_p scop,
1369 clay_array_p beta,
1370 unsigned int access_ident,
1371 clay_array_p neworder,
1372 clay_options_p options) {
1373
1374 /* Description
1375 * Swap the columns in the output dims (access arrays)
1376 * The first output dim is not used ( => access name)
1377 */
1378
1379 // core of the function : clay_dimreorder_aux
1380
1381 return clay_util_foreach_access(scop, beta, access_ident,
1382 clay_dimreorder_aux, neworder, 1);
1383 }
1384
1385
1386 static int clay_dimprivatize_aux(osl_relation_list_p access, void *args) {
1387 int depth = *((int*) args);
1388 osl_relation_p a = access->elt;
1389
1390 // check if the iterator is not used
1391 int i;
1392 for (i = 0 ; i < a->nb_rows ; i++) {
1393 if (!osl_int_zero(a->precision, a->m[i][a->nb_output_dims + depth])) {
1394 fprintf(stderr,
1395 "[Clay] Warning: can't privatize this statement\n"
1396 " the dim (depth=%d) seems to be already used\n"
1397 " the depth is the depth in the loops\n"
1398 " ", depth);
1399 return CLAY_ERROR_CANT_PRIVATIZE;
1400 }
1401 }
1402
1403 a->nb_output_dims++;
1404
1405 osl_relation_insert_blank_column(a, a->nb_output_dims);
1406 osl_relation_insert_blank_row(a, a->nb_rows);
1407
1408 osl_int_set_si(a->precision,
1409 &a->m[a->nb_rows-1][a->nb_output_dims],
1410 -1);
1411
1412 osl_int_set_si(a->precision,
1413 &a->m[a->nb_rows-1][a->nb_output_dims + depth],
1414 1);
1415
1416 return CLAY_SUCCESS;
1417 }
1418
1419
1420 /**
1421 * clay_dimprivatize function:
1422 * Privatize an access
1423 * \param[in,out] scop
1424 * \param[in] beta
1425 * \param[in] access_ident ident of the access array
1426 * \param[in] depth
1427 * \param[in] options
1428 * \return Status
1429 */
1430 int clay_dimprivatize(osl_scop_p scop,
1431 clay_array_p beta,
1432 unsigned int access_ident,
1433 unsigned int depth,
1434 clay_options_p options) {
1435
1436 /* Description
1437 * Add an output dim on each access which are in the beta vector
1438 */
1439
1440 if (depth <= 0)
1441 return CLAY_ERROR_DEPTH_OVERFLOW;
1442
1443 osl_statement_p stmt = clay_beta_find(scop->statement, beta);
1444 if (!stmt)
1445 return CLAY_ERROR_BETA_NOT_FOUND;
1446
1447 // FIXME: asserting that depth holds for any scattering
1448 osl_relation_p scattering = stmt->scattering;
1449 for ( ; scattering != NULL; scattering = scattering->next) {
1450 CLAY_BETA_CHECK_DEPTH(beta, depth, scattering);
1451 }
1452
1453 // core of the function : clay_dimprivatize_aux
1454
1455 return clay_util_foreach_access(scop, beta, access_ident,
1456 clay_dimprivatize_aux, &depth, 1);
1457 }
1458
1459
1460 static int clay_dimcontract_aux(osl_relation_list_p access, void *args) {
1461 int depth = *((int*) args);
1462 osl_relation_p a = access->elt;
1463
1464 int row = clay_util_relation_get_line(a, depth);
1465 if (row != -1) {
1466 osl_relation_remove_row(a, row);
1467 osl_relation_remove_column(a, depth+1); // remove output dim
1468 a->nb_output_dims--;
1469 }
1470
1471 return CLAY_SUCCESS;
1472 }
1473
1474
1475 /**
1476 * clay_dimcontract function:
1477 * Contract an access (remove a dimension)
1478 * \param[in,out] scop
1479 * \param[in] beta
1480 * \param[in] access_ident ident of the access array
1481 * \param[in] depth
1482 * \param[in] options
1483 * \return Status
1484 */
1485 int clay_dimcontract(osl_scop_p scop,
1486 clay_array_p beta,
1487 unsigned int access_ident,
1488 unsigned int depth,
1489 clay_options_p options) {
1490 /* Description
1491 * Remove the line/column at the depth level
1492 */
1493
1494 if (depth <= 0)
1495 return CLAY_ERROR_DEPTH_OVERFLOW;
1496
1497 osl_statement_p stmt = clay_beta_find(scop->statement, beta);
1498 if (!stmt)
1499 return CLAY_ERROR_BETA_NOT_FOUND;
1500
1501 // FIXME: asserting that depth holds for any scattering
1502 osl_relation_p scattering = stmt->scattering;
1503 for ( ; scattering != NULL; scattering = scattering->next) {
1504 CLAY_BETA_CHECK_DEPTH(beta, depth, scattering);
1505 }
1506
1507 // core of the function : clay_dimcontract_aux
1508
1509 return clay_util_foreach_access(scop, beta, access_ident,
1510 clay_dimcontract_aux, &depth, 1);
1511 }
1512
1513
1514 /**
1515 * clay_add_array function:
1516 * Add a new array in the arrays extensions.
1517 * \param[in,out] scop
1518 * \param[in] name string name
1519 * \param[in] result return the new id
1520 * \param[in] options
1521 * \return Status
1522 */
1523 int clay_add_array(osl_scop_p scop,
1524 char *name,
1525 int *result,
1526 clay_options_p options) {
1527
1528 osl_arrays_p arrays = osl_generic_lookup(scop->extension, OSL_URI_ARRAYS);
1529 if (!arrays)
1530 return CLAY_ERROR_ARRAYS_EXT_EMPTY;
1531
1532 int i;
1533 int sz = arrays->nb_names;
1534
1535 if (sz == 0)
1536 return CLAY_SUCCESS;
1537
1538 for (i = 0 ; i < sz ; i++)
1539 if (strcmp(arrays->names[i], name) == 0)
1540 return CLAY_ERROR_ID_EXISTS;
1541
1542 int id = arrays->id[0];
1543
1544 for (i = 1 ; i < sz ; i++)
1545 if (arrays->id[i] > id)
1546 id = arrays->id[i];
1547
1548 arrays->nb_names++;
1549
1550 // I don't know why, there is a valgrind warning when I use CLAY_realloc
1551 arrays->id = realloc(arrays->id, sizeof(int) * (sz+1));
1552 arrays->names = realloc(arrays->names, sizeof(char*) * (sz+1));
1553
1554 id++;
1555
1556 arrays->id[sz] = id;
1557 arrays->names[sz] = strdup(name);
1558
1559 *result = id;
1560
1561 return CLAY_SUCCESS;
1562 }
1563
1564 /**
1565 * clay_get_array_id function:
1566 * Search the array name in the arrays extension
1567 * \param[in,out] scop
1568 * \param[in] name string name
1569 * \param[in] result return the id
1570 * \param[in] options
1571 * \return Status
1572 */
1573 int clay_get_array_id(osl_scop_p scop,
1574 char *name,
1575 int *result,
1576 clay_options_p options) {
1577
1578 osl_arrays_p arrays = osl_generic_lookup(scop->extension, OSL_URI_ARRAYS);
1579 if (!arrays)
1580 return CLAY_ERROR_ARRAYS_EXT_EMPTY;
1581
1582 int i;
1583 int sz = arrays->nb_names;
1584 int id = -1;
1585
1586 for (i = 0 ; i < sz ; i++)
1587 if (strcmp(arrays->names[i], name) == 0) {
1588 id = arrays->id[i];
1589 break;
1590 }
1591
1592 if (id == -1)
1593 return CLAY_ERROR_ARRAY_NOT_FOUND;
1594
1595 *result = id;
1596
1597 return CLAY_SUCCESS;
1598 }
1599
1600
1601 static int clay_replace_array_aux(osl_relation_list_p access, void *args) {
1602 int new_id = *((int*) args);
1603 osl_relation_p a = access->elt;
1604
1605 // here row is != -1, because the function aux shouldn't be called
1606 int row = clay_util_relation_get_line(a, 0);
1607 osl_int_set_si(a->precision, &a->m[row][a->nb_columns-1], new_id);
1608
1609 return CLAY_SUCCESS;
1610 }
1611
1612 /**
1613 * clay_replace_array function:
1614 * Replace an ident array by another in each access
1615 * \param[in,out] scop
1616 * \param[in] last_id
1617 * \param[in] new_id
1618 * \param[in] options
1619 * \return Status
1620 */
1621 int clay_replace_array(osl_scop_p scop,
1622 unsigned int last_id,
1623 unsigned int new_id,
1624 clay_options_p options) {
1625
1626 // core of the function : clay_replace_array_aux
1627
1628 clay_array_p beta = clay_array_malloc();
1629 int ret = clay_util_foreach_access(scop, beta, last_id,
1630 clay_replace_array_aux, &new_id, 1);
1631 clay_array_free(beta);
1632
1633 return ret;
1634 }
1635
1636
1637 /**
1638 * clay_datacopy function:
1639 * This function will generate a loop to copy all data from the array
1640 * `array_id_original' to a new array `array_id_copy'. Use the function
1641 * add_array to insert a new array in the scop. A domain and a scattering
1642 * is needed to generate the loop to copy the data. They is a copy
1643 * from the domain/scattering of the first statement which corresponds
1644 * to the `beta_get_domain'. There is just a modification on the domain to
1645 * remove unused loops (iter >= 1 && iter <= -1 is set). The orignal id or
1646 * the copy id must be in this beta (in the list of access relation). Genarally
1647 * you will use replace_array before calling datacopy, that's why the
1648 * array_id_copy can be in the scop. The first access relation which is found
1649 * will be used to generate an access for the original id and the copy id.
1650 * \param[in,out] scop
1651 * \param[in] array_id_copy new variable
1652 * \param[in] array_id_original
1653 * \param[in] beta the loop is insert after the beta
1654 * \param[in] beta_get_domain domain/scattering are copied from this beta
1655 * the original or copy id must be in the list of
1656 * access of this beta
1657 * \param[in] options
1658 * \return Status
1659 */
1660 int clay_datacopy(osl_scop_p scop,
1661 unsigned int array_id_copy,
1662 unsigned int array_id_original,
1663 clay_array_p beta_insert,
1664 int insert_before,
1665 clay_array_p beta_get_domain,
1666 clay_options_p options) {
1667
1668 /* Description
1669 * - search the statement S beta_get_domain
1670 * - search the array array_id_original or array_id_copy in the list of
1671 * access in the given statement
1672 * - clone the found access array
1673 * - reclone this access and put the other array id (it depends which
1674 * id is found in the second step)
1675 * - search the beta_insert
1676 * - shift all the beta after or before beta_insert to let the place of the
1677 * new statement
1678 * - copy domain + scattering of S in a new statement (and add this one in
1679 * the scop)
1680 * - for each unused iterators we put iter >= 1 && iter <= -1 in the domain
1681 * to remove the loop at the generation of code
1682 * - put the 2 access arrays in this statement
1683 * - generate body
1684 */
1685
1686 osl_relation_p scattering, ptr = NULL;
1687 int row, i, j;
1688
1689 // TODO : global vars ??
1690 osl_arrays_p arrays;
1691 osl_scatnames_p scatnames;
1692 osl_strings_p params;
1693 osl_body_p body = NULL;
1694 osl_extbody_p extbody = NULL;
1695 int is_extbody = 0;
1696 osl_generic_p gen = NULL;
1697 arrays = osl_generic_lookup(scop->extension, OSL_URI_ARRAYS);
1698 scatnames = osl_generic_lookup(scop->extension, OSL_URI_SCATNAMES);
1699 params = osl_generic_lookup(scop->parameters, OSL_URI_STRINGS);
1700
1701 if (beta_insert->size == 0)
1702 return CLAY_ERROR_BETA_EMPTY;
1703
1704 // search the beta where we have to insert the new loop
1705 osl_statement_p stmt_1 = clay_beta_find(scop->statement, beta_insert);
1706 if (!stmt_1)
1707 return CLAY_ERROR_BETA_NOT_FOUND;
1708
1709 // search the beta which is need to copy the domain and scattering
1710 osl_statement_p stmt_2 = clay_beta_find(scop->statement, beta_get_domain);
1711 if (!stmt_2)
1712 return CLAY_ERROR_BETA_NOT_FOUND;
1713
1714 // copy the domain/scattering
1715 osl_statement_p copy = osl_statement_malloc();
1716 copy->domain = osl_relation_clone(stmt_2->domain);
1717 //copy->scattering = osl_relation_clone(stmt_2->scattering);
1718 copy->scattering = NULL;
1719 scattering = stmt_2->scattering;
1720 while (scattering != NULL) {
1721 if (clay_beta_check_relation(scattering, beta_get_domain)) {
1722 if (ptr == NULL) {
1723 copy->scattering = osl_relation_nclone(scattering, 1);
1724 ptr = copy->scattering;
1725 } else {
1726 ptr->next = osl_relation_nclone(scattering, 1);
1727 ptr = ptr->next;
1728 }
1729 }
1730 scattering = scattering->next;
1731 }
1732
1733 // create an extbody and copy the original iterators
1734 osl_extbody_p ebody = osl_extbody_malloc();
1735 ebody->body = osl_body_malloc();
1736
1737 // body string (it will be regenerated)
1738 ebody->body->expression = osl_strings_encapsulate(strdup("@ = @;"));
1739
1740 // copy iterators
1741 extbody = osl_generic_lookup(stmt_2->extension, OSL_URI_EXTBODY);
1742 if (extbody) {
1743 ebody->body->iterators = osl_strings_clone(extbody->body->iterators);
1744 is_extbody = 1;
1745 }
1746 else {
1747 body = osl_generic_lookup(stmt_2->extension, OSL_URI_BODY);
1748 ebody->body->iterators = osl_strings_clone(body->iterators);
1749 }
1750
1751 // 2 access coordinates
1752 osl_extbody_add(ebody, 0, 1);
1753 osl_extbody_add(ebody, 4, 1);
1754
1755 gen = osl_generic_shell(ebody, osl_extbody_interface());
1756 osl_generic_add(&copy->extension, gen);
1757 // not creating a ebody's corresponding "body" in the new copy statement
1758
1759
1760 // search the array_id in the beta_get_domain
1761
1762 osl_relation_list_p access = stmt_2->access;
1763 osl_relation_p a;
1764 int id;
1765
1766 while (access) {
1767 a = access->elt;
1768 id = osl_relation_get_array_id(a);
1769 if (id == array_id_original || id == array_id_copy)
1770 break;
1771 access = access->next;
1772 }
1773
1774 if (!access)
1775 return CLAY_ERROR_ARRAY_NOT_FOUND_IN_THE_BETA;
1776
1777 // matrix of the copied array
1778 a = osl_relation_nclone(a, 1);
1779 a->type = OSL_TYPE_WRITE;
1780 osl_int_set_si(a->precision, &a->m[0][a->nb_columns-1], array_id_copy);
1781 copy->access = osl_relation_list_malloc();
1782 copy->access->elt = a;
1783
1784 clay_util_body_regenerate_access(ebody, a, 0, arrays, scatnames, params);
1785
1786 // matrix of the original array
1787 a = osl_relation_nclone(a, 1);
1788 a->type = OSL_TYPE_READ;
1789 copy->access->next = osl_relation_list_malloc();
1790 copy->access->next->elt = a;
1791 copy->access->next->next = NULL;
1792 osl_int_set_si(a->precision, &a->m[0][a->nb_columns-1], array_id_original);
1793
1794 clay_util_body_regenerate_access(ebody, a, 1, arrays, scatnames, params);
1795
1796
1797 // remove the unused dim in the scatterin (modify the domain of the loop)
1798 for (j = 0 ; j < a->nb_input_dims ; j++) {
1799 int found = 0;
1800
1801 // search an unused input dims (if there is only 0 on the row)
1802 for (i = 0 ; i < a->nb_rows ; i++) {
1803 if (!osl_int_zero(a->precision, a->m[i][1 + a->nb_output_dims + j])) {
1804 found = 1;
1805 break;
1806 }
1807 }
1808
1809 // unused
1810 if (!found) {
1811 int k, t;
1812 osl_relation_p domain = copy->domain;
1813 for (i = 0 ; i < domain->nb_rows ; i++) {
1814 t = osl_int_get_si(domain->precision, domain->m[i][1 + j]);
1815
1816 if (t != 0) {
1817 for (k = 1 ; k < domain->nb_columns-1 ; k++)
1818 if (k != 1+j)
1819 osl_int_set_si(domain->precision, &domain->m[i][k], 0);
1820
1821 // set iter <= -1 && iter >= 1 ==> no solutions, so no loop !
1822 if (t > 0)
1823 osl_int_set_si(domain->precision, &domain->m[i][k], -1);
1824 else
1825 osl_int_set_si(domain->precision, &domain->m[i][k], 1);
1826 }
1827 }
1828 }
1829 }
1830
1831
1832 // let the place to the new loop
1833
1834 scattering = copy->scattering;
1835 if (insert_before) {
1836 clay_beta_shift_before(scop->statement, beta_insert, 1);
1837
1838 // set the beta : it's the beta[0]
1839 while (scattering != NULL) {
1840 // we know that copy has only scattering union parts that match the
1841 // requested beta.
1842 row = clay_util_relation_get_line(scattering, 0);
1843 osl_int_set_si(scattering->precision,
1844 &scattering->m[row][scattering->nb_columns-1],
1845 beta_insert->data[0]);
1846 scattering = scattering->next;
1847 }
1848 } else {
1849 clay_beta_shift_after(scop->statement, beta_insert, 1);
1850
1851 // set the beta : it's the beta[0] + 1
1852 while (scattering != NULL) {
1853 row = clay_util_relation_get_line(scattering, 0);
1854 osl_int_set_si(scattering->precision,
1855 &scattering->m[row][scattering->nb_columns-1],
1856 beta_insert->data[0]+1);
1857 scattering = scattering->next;
1858 }
1859 }
1860
1861 copy->next = scop->statement;
1862 scop->statement = copy;
1863
1864 if (options && options->normalize)
1865 clay_beta_normalize(scop);
1866
1867 return CLAY_SUCCESS;
1868 }
1869
1870
1871 /**
1872 * clay_block function:
1873 * \param[in,out] scop
1874 * \param[in] beta_stmt1
1875 * \param[in] beta_stmt2
1876 * \param[in] options
1877 * \return Status
1878 */
1879 int clay_block(osl_scop_p scop,
1880 clay_array_p beta_stmt1,
1881 clay_array_p beta_stmt2,
1882 clay_options_p options) {
1883
1884 /* Description
1885 * concat '{' + body(stmt_1) + body(stmt_2) + '}'
1886 * update extbody if needed
1887 * concat access(stmt_1) + access(stmt_2)
1888 * remove stmt_2
1889 */
1890 if (beta_stmt1->size != beta_stmt2->size)
1891 return CLAY_ERROR_BETAS_NOT_SAME_DIMS;
1892
1893 // search statements and check betas
1894 osl_statement_p stmt_1 = clay_beta_find(scop->statement, beta_stmt1);
1895 if (!stmt_1)
1896 return CLAY_ERROR_BETA_NOT_FOUND;
1897
1898 osl_statement_p stmt_2 = clay_beta_find(scop->statement, beta_stmt2);
1899 if (!stmt_2)
1900 return CLAY_ERROR_BETA_NOT_FOUND;
1901
1902 // We can only merge full statements, because we change the body so it would
1903 // affect other parts with different scatterings.
1904 osl_relation_p scattering = stmt_1->scattering;
1905 while (scattering != NULL) {
1906 CLAY_BETA_IS_STMT(beta_stmt1, scattering);
1907 scattering = scattering->next;
1908 }
1909 scattering = stmt_2->scattering;
1910 while (scattering != NULL) {
1911 CLAY_BETA_IS_STMT(beta_stmt2, scattering);
1912 scattering = scattering->next;
1913 }
1914
1915 if (!osl_relation_equal(stmt_1->domain, stmt_2->domain))
1916 return CLAY_ERROR_BETAS_NOT_SAME_DOMAIN;
1917
1918 int i;
1919 int is_extbody_1 = 0;
1920 int is_extbody_2 = 0;
1921
1922 char **expr_left;
1923 char **expr_right;
1924 char *new_expr;
1925
1926 osl_extbody_p ebody_1, ebody_2;
1927 osl_body_p body_1, body_2;
1928 osl_generic_p gen = NULL;
1929
1930 // get the body string
1931
1932 ebody_1 = osl_generic_lookup(stmt_1->extension, OSL_URI_EXTBODY);
1933 if (ebody_1) {
1934 is_extbody_1 = 1;
1935 }
1936 else {
1937 body_1 = osl_generic_lookup(stmt_1->extension, OSL_URI_BODY);
1938 }
1939
1940 ebody_2 = osl_generic_lookup(stmt_2->extension, OSL_URI_EXTBODY);
1941 if (ebody_2) {
1942 is_extbody_2 = 1;
1943 }
1944 else {
1945 body_2 = osl_generic_lookup(stmt_2->extension, OSL_URI_BODY);
1946 }
1947
1948 if (is_extbody_1 != is_extbody_2)
1949 return CLAY_ERROR_ONE_HAS_EXTBODY;
1950
1951
1952 expr_left = is_extbody_1
1953 ? ebody_1->body->expression->string
1954 : body_1->expression->string;
1955
1956 expr_right = is_extbody_2
1957 ? ebody_2->body->expression->string
1958 : body_2->expression->string;
1959
1960 // update extbody
1961 if (is_extbody_1) {
1962
1963 // shift for the '{'
1964 for (i = 0 ; i < ebody_1->nb_access ; i++) {
1965 if (ebody_1->start[i] != -1)
1966 ebody_1->start[i]++;
1967 }
1968
1969 int offset = 1 + strlen(expr_left[0]);
1970
1971 // shift the right part
1972 for (i = 0 ; i < ebody_2->nb_access ; i++) {
1973 if (ebody_2->start[i] != -1)
1974 ebody_2->start[i] += offset;
1975
1976 // concat with the extbody 2
1977 osl_extbody_add(ebody_1, ebody_2->start[i], ebody_2->length[i]);
1978 }
1979
1980 }
1981
1982 // generate the new body string
1983 new_expr = (char*) malloc(strlen(expr_left[0]) + strlen(expr_right[0]) + 3);
1984 strcpy(new_expr, "{");
1985 strcat(new_expr, expr_left[0]);
1986 strcat(new_expr, expr_right[0]);
1987 strcat(new_expr, "}");
1988
1989 free(expr_left[0]);
1990 expr_left[0] = new_expr;
1991
1992 // concat all the access array
1993 osl_relation_list_p access = stmt_1->access;
1994 if (access) {
1995 while (access->next)
1996 access = access->next;
1997 }
1998 access->next = stmt_2->access;
1999 stmt_2->access = NULL;
2000
2001 // synchronize extbody with body for stmt_1
2002 if (is_extbody_1) {
2003 body_1 = osl_generic_lookup(stmt_1->extension, OSL_URI_BODY);
2004 if (body_1) {
2005 osl_generic_remove(&stmt_1->extension, OSL_URI_BODY);
2006 body_1 = osl_body_clone(ebody_1->body);
2007 gen = osl_generic_shell(body_1, osl_body_interface());
2008 osl_generic_add(&stmt_1->extension, gen);
2009 }
2010 }
2011
2012 // Remove the scattering parts of stmt_2 that match the beta2.
2013 scattering = stmt_2->scattering;
2014 if (scattering) {
2015 if (clay_beta_check_relation(scattering, beta_stmt2)) {
2016 osl_relation_p to_delete = scattering;
2017 to_delete->next = NULL;
2018 stmt_2->scattering = scattering->next;
2019 scattering = scattering->next;
2020 osl_relation_free(to_delete);
2021 }
2022 }
2023 // These branches must not be merged, scattering is overwritten inside!
2024 if (scattering) {
2025 while (scattering->next != NULL) {
2026 osl_relation_p to_delete = NULL;
2027 if (clay_beta_check_relation(scattering->next, beta_stmt2)) {
2028 to_delete = scattering->next;
2029 to_delete->next = NULL;
2030 scattering->next = scattering->next->next;
2031 }
2032 scattering = scattering->next;
2033 osl_relation_free(to_delete);
2034 }
2035 }
2036 // Remove stmt_2 completely if it has no more scatterings (i.e. was only a statement).
2037 if (stmt_2->scattering == NULL) {
2038 osl_statement_p s = scop->statement;
2039 if (s != NULL) {
2040 if (s == stmt_2) {
2041 scop->statement = s->next;
2042 stmt_2->next = NULL;
2043 osl_statement_free(stmt_2);
2044 stmt_2 = NULL;
2045 s = s->next;
2046 }
2047 }
2048 if (s != NULL && stmt_2 != NULL) {
2049 while (s->next != NULL) {
2050 if (s->next == stmt_2) {
2051 s->next = s->next->next;
2052 stmt_2->next = NULL; // prevent free from removing chained statements
2053 osl_statement_free(stmt_2);
2054 break;
2055 }
2056 s = s->next;
2057 }
2058 }
2059 }
2060
2061 if (options && options->normalize)
2062 clay_beta_normalize(scop);
2063
2064 return CLAY_SUCCESS;
2065 }
Clay, the Chunky Loop Alteration wizardrY: a scripting system for high-level loop transformations