Lines Matching refs:loop
5 ** loop.c **
86 * Displays a loop structure in a way that trends to be understandable without
96 void cloog_loop_print_structure(FILE * file, CloogLoop * loop, int level)
99 if (loop)
107 /* For each loop. */
108 while (loop)
125 cloog_domain_print_structure(file, loop->domain, level+1, "CloogDomain");
130 if (loop->stride) {
132 cloog_int_print(file, loop->stride->stride);
135 cloog_int_print(file, loop->stride->offset);
145 cloog_block_print_structure(file,loop->block,level+1) ;
153 if (loop->inner)
154 cloog_loop_print_structure(file,loop->inner,level+1) ;
157 loop = loop->next ;
160 if (!loop)
170 { /* A special blank line if the is a next loop. */
187 void cloog_loop_print(FILE * file, CloogLoop * loop)
188 { cloog_loop_print_structure(file,loop,0) ;
199 * This function frees the allocated memory for a CloogLoop structure (loop),
203 void cloog_loop_free(CloogLoop * loop)
206 while (loop != NULL) {
207 cloog_loop_leak_down(loop->state);
209 next = loop->next ;
210 cloog_domain_free(loop->domain) ;
211 cloog_domain_free(loop->unsimplified);
212 cloog_block_free(loop->block) ;
213 if (loop->inner != NULL)
214 cloog_loop_free(loop->inner) ;
216 cloog_stride_free(loop->stride);
217 free(loop) ;
218 loop = next ;
226 * structure (loop), each other argument is a boolean having to be set to 1 if
232 void cloog_loop_free_parts(loop, domain, block, inner, next)
233 CloogLoop * loop ;
237 while (loop != NULL) {
238 cloog_loop_leak_down(loop->state);
239 follow = loop->next ;
242 cloog_domain_free(loop->domain) ;
245 cloog_block_free(loop->block) ;
247 if ((inner) && (loop->inner != NULL))
248 cloog_loop_free_parts(loop->inner,domain,block,inner,1) ;
250 cloog_domain_free(loop->unsimplified);
251 cloog_stride_free(loop->stride);
252 free(loop) ;
254 loop = follow ;
256 loop = NULL ;
274 CloogLoop * loop ;
278 loop = cloog_loop_malloc(state);
280 loop->domain = domain;
281 if (loop->domain != NULL)
282 nb_iterators = cloog_domain_dimension(loop->domain);
287 loop->block = cloog_block_alloc(statement, 0, NULL, nb_iterators);
289 return loop ;
295 * This function reads loop data from a file (foo, possibly stdin) and
297 * This function can be used only for input file reading, when one loop is
299 * - number is the statement block number carried by the loop (-1 if none).
338 { CloogLoop * loop ;
341 loop = (CloogLoop *)malloc(sizeof(CloogLoop)) ;
342 if (loop == NULL)
348 loop->state = state;
349 loop->domain = NULL ;
350 loop->unsimplified = NULL;
351 loop->block = NULL ;
352 loop->usr = NULL;
353 loop->inner = NULL ;
354 loop->next = NULL ;
355 loop->otl = 0;
356 loop->stride = NULL;
358 return loop ;
374 { CloogLoop * loop ;
376 loop = cloog_loop_malloc(state);
378 loop->domain = domain ;
379 loop->block = block ;
380 loop->inner = inner ;
381 loop->next = next ;
382 loop->otl = otl;
383 loop->stride = cloog_stride_copy(stride);
385 return(loop) ;
391 * This function adds a CloogLoop structure (loop) at a given place (now) of a
393 * is (start). This function updates (now) to (loop), and updates (start) if the
397 void cloog_loop_add(CloogLoop ** start, CloogLoop ** now, CloogLoop * loop)
399 { *start = loop ;
403 { (*now)->next = loop ;
411 * This function adds a CloogLoop structure (loop) at a given place (now) of a
413 * is (start). This function updates (now) to the end of the loop list (loop),
418 void cloog_loop_add_list(CloogLoop ** start, CloogLoop ** now, CloogLoop * loop)
420 { *start = loop ;
424 { (*now)->next = loop ;
442 { CloogLoop * loop ;
446 loop = NULL ;
450 loop = cloog_loop_alloc(source->state, domain, source->otl,
452 loop->usr = source->usr;
453 loop->inner = cloog_loop_copy(source->inner) ;
454 loop->next = cloog_loop_copy(source->next) ;
456 return(loop) ;
464 * is (start). (loop) can be an union of polyhedra, this function separates the
468 * (loop) can be freed by this function, basically when its domain is actually
478 void cloog_loop_add_disjoint(start, now, loop)
479 CloogLoop ** start, ** now, * loop ;
485 if (cloog_domain_isconvex(loop->domain))
486 cloog_loop_add(start,now,loop) ;
488 domain = cloog_domain_simplify_union(loop->domain);
489 loop->domain = NULL ;
495 sep = cloog_loop_alloc(loop->state, domain, 0, NULL,
496 loop->block, loop->inner, NULL);
510 /* Each new loop will have its own life, for instance we can free its
511 * inner loop and included block. Then each one must have its own copy
514 inner = cloog_loop_copy(loop->inner) ;
515 block = cloog_block_copy(loop->block) ;
517 sep = cloog_loop_alloc(loop->state, cloog_domain_copy(domain),
534 cloog_loop_free_parts(loop,0,0,0,0) ;
541 * This function returns a list of loops such that each loop with non-convex
542 * domain in the input list (loop) is separated into several loops where the
548 CloogLoop * cloog_loop_disjoint(CloogLoop * loop)
552 if (loop && !loop->next && cloog_domain_isconvex(loop->domain))
553 return loop ;
555 while (loop != NULL)
556 { next = loop->next ;
557 loop->next = NULL ;
558 cloog_loop_add_disjoint(&res,&now,loop) ;
559 loop = next ;
568 * This function returns the (loop) in the context of (context): it makes the
569 * intersection between the (loop) domain and the (context), then it returns
570 * a pointer to a new loop, with this intersection as domain.
576 CloogLoop *cloog_loop_restrict(CloogLoop *loop, CloogDomain *context)
581 domain = loop->domain ;
586 new_domain = cloog_domain_intersection(extended_context,loop->domain) ;
590 new_domain = cloog_domain_intersection(context,loop->domain) ;
597 new_loop = cloog_loop_alloc(loop->state, new_domain,
598 0, NULL, loop->block, loop->inner, NULL);
605 * Call cloog_loop_restrict on each loop in the list "loop" and return
608 CloogLoop *cloog_loop_restrict_all(CloogLoop *loop, CloogDomain *context)
614 for (; loop; loop = next) {
615 next = loop->next;
617 *res_next = cloog_loop_restrict(loop, context);
620 cloog_loop_free_parts(loop, 1, 0, 0, 0);
622 loop->next = NULL;
623 cloog_loop_free(loop);
632 * Restrict the domains of the inner loops of each loop l in the given
633 * list of loops to the domain of the loop l. If the domains of all
634 * inner loops of a given loop l turn out to be empty, then remove l
637 CloogLoop *cloog_loop_restrict_inner(CloogLoop *loop)
643 for (; loop; loop = next) {
644 next = loop->next;
646 loop->inner = cloog_loop_restrict_all(loop->inner, loop->domain);
647 if (loop->inner) {
648 *res_next = loop;
651 loop->next = NULL;
652 cloog_loop_free(loop);
663 * This function returns the projection of (loop) on the (level) first
664 * dimensions (outer loops). It makes the projection of the (loop) domain,
665 * then it returns a pointer to a new loop, with this projection as domain.
671 CloogLoop * cloog_loop_project(CloogLoop * loop, int level)
676 copy = cloog_loop_alloc(loop->state, loop->domain, loop->otl, loop->stride,
677 loop->block, loop->inner, NULL);
679 if (cloog_domain_dimension(loop->domain) == level)
680 new_domain = cloog_domain_copy(loop->domain) ;
682 new_domain = cloog_domain_project(loop->domain, level);
684 new_loop = cloog_loop_alloc(loop->state, new_domain, 0, NULL,
692 * Call cloog_loop_project on each loop in the list "loop" and return
695 CloogLoop *cloog_loop_project_all(CloogLoop *loop, int level)
701 for (; loop; loop = next) {
702 next = loop->next;
704 *res_next = cloog_loop_project(loop, level);
706 cloog_loop_free_parts(loop, 0, 0, 0, 0);
720 { CloogLoop * loop, * temp ;
722 loop = a ;
723 temp = loop ;
724 if (loop != NULL)
730 loop = b ;
732 return(loop) ;
739 * a single loop with the concatenation of their inner loops
740 * as inner loop.
742 CloogLoop *cloog_loop_combine(CloogLoop *loop)
746 for (first = loop; first; first = first->next) {
757 return loop;
763 CloogLoop *cloog_loop_remove_empty_domain_loops(CloogLoop *loop)
769 for (l = loop; l; l = next) {
783 CloogLoop *cloog_loop_decompose_inner(CloogLoop *loop,
786 /* For each loop with only one inner loop, replace the domain
787 * of the loop with the projection of the domain of the inner
788 * loop. To increase the number of loops with a single inner
792 CloogLoop *cloog_loop_specialize(CloogLoop *loop,
799 loop = cloog_loop_decompose_inner(loop, level, scalar,
802 for (l = loop; l; l = l->next) {
818 return cloog_loop_remove_empty_domain_loops(loop);
821 /* For each loop with only one inner loop, propagate the bounds from
822 * the inner loop domain to the outer loop domain. This is especially
823 * useful if the inner loop domain has a non-trivial stride which
826 CloogLoop *cloog_loop_propagate_lower_bound(CloogLoop *loop, int level)
832 for (l = loop; l; l = l->next) {
848 return loop;
854 * loops: for a given set of polyhedra (loop), it computes a set of disjoint
859 * loop, redundant constraints are fired.
863 * there is only one loop in the list (seems to work
867 CloogLoop * cloog_loop_separate(CloogLoop * loop)
873 if (loop == NULL)
876 loop = cloog_loop_combine(loop);
878 if (loop->next == NULL)
879 return cloog_loop_disjoint(loop) ;
881 UQ = cloog_domain_copy(loop->domain) ;
882 domain = cloog_domain_copy(loop->domain) ;
883 res = cloog_loop_alloc(loop->state, domain, 0, NULL,
884 loop->block, loop->inner, NULL);
886 old = loop ;
887 while((loop = loop->next) != NULL)
890 /* For all Q, add Q-loop associated with the blocks of Q alone,
891 * and Q inter loop associated with the blocks of Q and loop.
894 /* Add (Q inter loop). */
895 if ((disjoint = cloog_domain_lazy_disjoint(Q->domain,loop->domain)))
898 { if ((lazy_equal = cloog_domain_lazy_equal(Q->domain,loop->domain)))
901 domain = cloog_domain_intersection(Q->domain,loop->domain) ;
905 cloog_loop_copy(loop->inner)) ;
906 new_loop = cloog_loop_alloc(loop->state, domain, 0, NULL,
916 /* Add (Q - loop). */
923 domain = cloog_domain_difference(Q->domain,loop->domain) ;
927 new_loop = cloog_loop_alloc(loop->state, domain, 0, NULL,
940 /* Add loop-UQ associated with the blocks of loop alone.*/
941 if (cloog_domain_lazy_disjoint(loop->domain,UQ))
942 domain = cloog_domain_copy(loop->domain) ;
944 { if (cloog_domain_lazy_equal(loop->domain,UQ))
947 domain = cloog_domain_difference(loop->domain,UQ) ;
951 new_loop = cloog_loop_alloc(loop->state, domain, 0, NULL,
952 NULL, loop->inner, NULL);
957 /* If loop->inner is no more useful, we can free it. */
958 cloog_loop_free(loop->inner) ;
961 loop->inner = NULL ;
963 if (loop->next != NULL)
964 UQ = cloog_domain_union(UQ, cloog_domain_copy(loop->domain));
996 CloogLoop *cloog_loop_merge(CloogLoop *loop, int level, CloogOptions *options)
1001 if (loop == NULL)
1002 return loop;
1004 if (loop->next == NULL && cloog_domain_isconvex(loop->domain))
1005 return loop;
1007 old = loop;
1008 temp = loop->domain;
1009 loop->domain = NULL;
1010 new_inner = loop->inner;
1012 for (loop = loop->next; loop; loop = loop->next) {
1013 temp = cloog_domain_union(temp, loop->domain);
1014 loop->domain = NULL;
1015 new_inner = cloog_loop_concat(new_inner, loop->inner);
1070 static int cloog_loop_count(CloogLoop *loop)
1074 for (nb_loops = 0; loop; loop = loop->next)
1088 CloogLoop *cloog_loop_sort(CloogLoop *loop, int level)
1096 return loop;
1099 nb_loops = cloog_loop_count(loop);
1101 /* If there is only one loop, it's the end. */
1103 return(loop) ;
1106 * - loop_array: the loop array,
1114 /* We fill up the loop and domain arrays. */
1115 for (i=0;i<nb_loops;i++,loop=loop->next)
1116 { loop_array[i] = loop ;
1141 * This function changes the loop list in such a way that we have no more than
1142 * one dimension added by level. It returns an equivalent loop list with
1149 CloogLoop *cloog_loop_nest(CloogLoop *loop, CloogDomain *context, int level)
1154 loop = cloog_loop_disjoint(loop);
1158 while (loop != NULL)
1159 { p = cloog_loop_restrict(loop, context);
1160 next = loop->next ;
1163 { cloog_loop_free_parts(loop,1,0,0,0) ;
1185 cloog_loop_free_parts(loop,1,1,1,0) ;
1187 loop = next ;
1201 static int cloog_loop_variable_offset_stride(CloogLoop *loop, int level)
1207 for (inner = loop->inner; inner; inner = inner->next) {
1221 loop->stride = stride;
1222 loop->domain = cloog_domain_stride_lower_bound(loop->domain, level, stride);
1230 * This function will find the stride of a loop for the iterator at the column
1233 * inner loops a common condition on this iterator for the inner loop iterators
1234 * to be integral. For instance, let us consider a loop with the iterator i,
1236 * The first inner loop has the constraint 3j=i, and the second one has the
1248 * - loop is the loop including the iteration domain of the considered iterator,
1255 void cloog_loop_stride(CloogLoop * loop, int level)
1260 if (!cloog_domain_can_stride(loop->domain, level))
1263 if (cloog_loop_variable_offset_stride(loop, level))
1277 inner = loop->inner ;
1313 loop->stride = cloog_stride_alloc(stride, offset);
1314 loop->domain = cloog_domain_stride_lower_bound(loop->domain, level,
1315 loop->stride);
1325 void cloog_loop_otl(CloogLoop *loop, int level)
1327 if (cloog_domain_is_otl(loop->domain, level))
1328 loop->otl = 1;
1334 * This function implements the 'stop' option : each domain of each loop
1335 * in the list 'loop' is replaced by 'context'. 'context' should be the
1336 * domain of the outer loop. By using this method, there are no more dimensions
1343 CloogLoop * cloog_loop_stop(CloogLoop * loop, CloogDomain * context)
1344 { if (loop == NULL)
1347 { cloog_domain_free(loop->domain) ;
1348 loop->domain = cloog_domain_copy(context) ;
1349 loop->next = cloog_loop_stop(loop->next, context) ;
1352 return loop ;
1367 * This function should be called on the innermost loop (the loop
1395 * This function returns 1 if loop 'l1' is greater than loop 'l2' for the
1397 * we want to know is whether a loop is scheduled before another one or not.
1423 * This function returns 1 if loop 'l1' is equal to loop 'l2' for the scalar
1448 * This function sorts a linked list of loops (loop) with respect to the
1453 * \param loop Loop list to sort.
1464 CloogLoop * cloog_loop_scalar_sort(loop, level, scaldims, nb_scattdims, scalar)
1465 CloogLoop * loop ;
1472 for (current = &loop; (*current)->next; current = &(*current)->next) {
1483 return loop ;
1497 CloogLoop *cloog_loop_generate_backtrack(CloogLoop *loop,
1504 temp = loop ;
1505 loop = NULL ;
1536 cloog_loop_add(&loop,&now,l) ;
1545 return loop ;
1552 int cloog_loop_more(CloogLoop *loop, int level, int scalar, int nb_scattdims)
1555 cloog_domain_dimension(loop->domain) >= level;
1566 int cloog_loop_is_constant(CloogLoop *loop, int level)
1574 if (!cloog_domain_lazy_isconstant(loop->domain, level - 1, &c1))
1577 for (loop = loop->next; r && loop; loop = loop->next) {
1578 if (!cloog_domain_lazy_isconstant(loop->domain, level - 1, &c2))
1591 * Assuming all domains in the given linked list of loop
1592 * have a fixed values at level, return a single loop with
1597 CloogLoop *cloog_loop_constant(CloogLoop *loop, int level)
1602 if (!loop)
1603 return loop;
1605 inner = loop->inner;
1606 domain = loop->domain;
1607 for (tmp = loop->next; tmp; tmp = tmp->next) {
1615 res = cloog_loop_alloc(loop->state, domain, 0, NULL, NULL, inner, NULL);
1617 cloog_loop_free_parts(loop, 0, 0, 0, 1);
1623 /* Unroll the given loop at the given level, provided it is allowed
1626 * loop. Otherwise, we simply return the original loop.
1628 static CloogLoop *loop_unroll(CloogLoop *loop, int level)
1640 can_unroll = cloog_domain_can_unroll(loop->domain, level, &n, &lb);
1643 return loop;
1649 domain = cloog_domain_copy(loop->domain);
1651 inner = cloog_loop_copy(loop->inner);
1657 *next_res = cloog_loop_alloc(loop->state, domain, 1, NULL, NULL,
1666 cloog_loop_free(loop);
1675 CloogLoop *cloog_loop_unroll(CloogLoop *loop, int level)
1681 for (now = loop; now; now = next) {
1694 CloogLoop *cloog_loop_generate_restricted_or_stop(CloogLoop *loop,
1699 CloogLoop *cloog_loop_recurse(CloogLoop *loop,
1705 * Recurse on the inner loops of the given single loop.
1707 * - loop is the loop for which we have to generate scanning code,
1712 * - constant is true if the loop is known to be executed at most once
1715 static CloogLoop *loop_recurse(CloogLoop *loop,
1723 cloog_loop_stride(loop, level);
1727 loop = cloog_loop_unroll(loop, level);
1728 if (loop->next)
1729 return cloog_loop_recurse(loop, level, scalar, scaldims,
1734 cloog_loop_otl(loop, level);
1735 inner = loop->inner;
1736 domain = cloog_domain_copy(loop->domain);
1737 domain = cloog_domain_add_stride_constraint(domain, loop->stride);
1765 loop->inner = into;
1766 return loop;
1771 * Recurse on the inner loops of each of the loops in the loop list.
1773 * - loop is the loop list for which we have to generate scanning code,
1778 * - constant is true if the loop is known to be executed at most once
1781 CloogLoop *cloog_loop_recurse(CloogLoop *loop,
1789 for (now = loop; now; now = next) {
1827 * this loop, and the max across all 'last' depths */
1828 void cloog_loop_get_fl(CloogLoop *loop, int *f, int *l,
1831 if (loop == NULL) return;
1833 CloogBlock *block = loop->block;
1839 cloog_loop_get_fl(loop->inner, f, l, options);
1840 cloog_loop_get_fl(loop->next, f, l, options);
1848 * - loop is the loop for which we have to generate a scanning code,
1865 * - May 31, 2012: statement-wise first and last depth for loop separation
1870 CloogLoop *cloog_loop_generate_general(CloogLoop *loop,
1884 cloog_loop_get_fl(loop, &first, &last, options);
1893 if (level > 0 && cloog_loop_is_constant(loop, level)) {
1894 res = cloog_loop_constant(loop, level);
1897 res = cloog_loop_merge(loop, level, options);
1899 res = cloog_loop_separate(loop);
1911 /* 4. Recurse for each loop with the current domain as context. */
1956 CloogLoop *cloog_loop_generate_restricted(CloogLoop *loop,
1971 * - loop is the loop for which we have to generate a scanning code,
1980 CloogLoop *cloog_loop_generate_scalar(CloogLoop *loop,
1986 /* We sort the loop list with respect to the current scalar vector. */
1987 res = cloog_loop_scalar_sort(loop,level,scaldims,nb_scattdims,scalar) ;
2027 /* Compare loop with the next loop based on their constant dimensions.
2029 * dimensions of loop are lexicographically smaller, equal or greater
2030 * than those of loop->next.
2031 * If loop is the last in the list, then it is assumed to be smaller
2034 static int cloog_loop_next_scal_cmp(CloogLoop *loop)
2039 if (!loop->next)
2042 nb_scaldims = loop->block->nb_scaldims;
2043 if (loop->next->block->nb_scaldims < nb_scaldims)
2044 nb_scaldims = loop->next->block->nb_scaldims;
2047 int cmp = cloog_int_cmp(loop->block->scaldims[i],
2048 loop->next->block->scaldims[i]);
2052 return loop->block->nb_scaldims - loop->next->block->nb_scaldims;
2091 /* Try to block adjacent loops in the loop list "loop".
2095 * dimensions strictly larger than the previous loop in the complete
2096 * list and such that the loop (end) after the last loop in the sublist
2097 * has constant dimensions strictly larger than the last loop in the sublist.
2109 CloogLoop *cloog_loop_block(CloogLoop *loop, int *scaldims, int nb_scattdims)
2115 if (!loop->next)
2116 return loop;
2117 for (begin = loop; begin; begin = begin->next) {
2119 return loop;
2121 return loop;
2125 for (begin = loop; begin; begin = begin->next) {
2150 return loop;
2277 * each loop should be executed before some iterations of the other loop.
2394 * pointed to by "loop".
2403 CloogLoop *cloog_loop_generate_components(CloogLoop *loop,
2413 if (level == 0 || !loop->next)
2414 return cloog_loop_generate_general(loop, level, scalar,
2417 nb_loops = cloog_loop_count(loop);
2422 for (i = 0, tmp = loop; i < nb_loops; i++, tmp = tmp->next)
2456 /* For each loop in the list "loop", decompose the list of
2460 CloogLoop *cloog_loop_decompose_inner(CloogLoop *loop,
2468 for (l = loop; l; l = l->next) {
2475 return loop;
2480 for (l = loop; l; l = l->next) {
2517 return loop;
2521 CloogLoop *cloog_loop_generate_restricted(CloogLoop *loop,
2530 return cloog_loop_generate_scalar(loop, level, scalar,
2534 * loop variable and the parameters.
2536 loop = cloog_loop_project_all(loop, level);
2538 return cloog_loop_generate_components(loop, level, scalar, scaldims,
2543 CloogLoop *cloog_loop_generate_restricted_or_stop(CloogLoop *loop,
2550 return cloog_loop_stop(loop,context) ;
2552 return cloog_loop_generate_restricted(loop, level, scalar, scaldims,
2562 * - loop is the loop for which we have to generate a scanning code,
2563 * - context is the context of the current loop (constraints on parameter and/or
2564 * on outer loop counters),
2573 * - June 15th 2005: a memory leak fixed (loop was not entirely freed when
2583 CloogLoop *cloog_loop_generate(CloogLoop *loop, CloogDomain *context,
2589 loop = cloog_loop_restrict_all(loop, context);
2590 if (!loop)
2593 return cloog_loop_generate_restricted_or_stop(loop, context,
2599 * Internal function for simplifying a single loop in a list of loops.
2602 static CloogLoop *loop_simplify(CloogLoop *loop, CloogDomain *context,
2610 domain = loop->domain ;
2620 cloog_loop_free(loop->inner);
2626 inner = cloog_loop_simplify(loop->inner, inter, level+1, nb_scattdims,
2629 if ((inner == NULL) && (loop->block == NULL)) {
2635 new_block = cloog_block_copy(loop->block) ;
2637 simplified = cloog_loop_alloc(loop->state, simp, loop->otl, loop->stride,
2641 inter = cloog_domain_add_stride_constraint(inter, loop->stride);
2658 * recursively simplifies each loop in the context of the preceding loop domain.
2659 * It returns a pointer to the simplified loop list.
2666 * - June 15th 2005: a memory leak fixed (loop was not conveniently freed
2676 CloogLoop *cloog_loop_simplify(CloogLoop *loop, CloogDomain *context, int level,
2684 for (now = loop; now; now = now->next)
2696 loop = cloog_loop_disjoint(loop);
2698 for (now = loop; now; now = now->next) {
2701 now->inner = NULL; /* For loop integrity. */
2708 cloog_loop_free(loop);
2716 * This function add the scattering (scheduling) informations in a loop.
2718 void cloog_loop_scatter(CloogLoop * loop, CloogScattering *scatt)
2720 loop->domain = cloog_domain_scatter(loop->domain, scatt);