* n is the number of nodes
* node is the list of nodes
* maxvar is the maximal number of variables over all nodes
+ * max_row is the allocated number of rows in the schedule
* n_row is the current (maximal) number of linearly independent
* rows in the node schedules
* n_total_row is the current number of rows in the node schedules
struct isl_sched_node *node;
int n;
int maxvar;
+ int max_row;
int n_row;
int *sorted;
isl_basic_set_free(graph->lp);
}
+/* For each "set" on which this function is called, increment
+ * graph->n by one and update graph->maxvar.
+ */
+static int init_n_maxvar(__isl_take isl_set *set, void *user)
+{
+ struct isl_sched_graph *graph = user;
+ int nvar = isl_set_dim(set, isl_dim_set);
+
+ graph->n++;
+ if (nvar > graph->maxvar)
+ graph->maxvar = nvar;
+
+ isl_set_free(set);
+
+ return 0;
+}
+
+/* Compute the number of rows that should be allocated for the schedule.
+ * The graph can be split at most "n - 1" times, there can be at most
+ * two rows for each dimension in the iteration domains (in particular,
+ * we usually have one row, but it may be split by split_scaled),
+ * and there can be one extra row for ordering the statements.
+ * Note that if we have actually split "n - 1" times, then no ordering
+ * is needed, so in principle we could use "graph->n + 2 * graph->maxvar - 1".
+ */
+static int compute_max_row(struct isl_sched_graph *graph,
+ __isl_keep isl_union_set *domain)
+{
+ graph->n = 0;
+ graph->maxvar = 0;
+ if (isl_union_set_foreach_set(domain, &init_n_maxvar, graph) < 0)
+ return -1;
+ graph->max_row = graph->n + 2 * graph->maxvar;
+
+ return 0;
+}
+
/* Add a new node to the graph representing the given set.
*/
static int extract_node(__isl_take isl_set *set, void *user)
graph->node[graph->n].nparam = nparam;
graph->node[graph->n].sched = sched;
graph->node[graph->n].sched_map = NULL;
- band = isl_alloc_array(ctx, int, graph->n_edge + nvar);
+ band = isl_alloc_array(ctx, int, graph->max_row);
graph->node[graph->n].band = band;
- band_id = isl_calloc_array(ctx, int, graph->n_edge + nvar);
+ band_id = isl_calloc_array(ctx, int, graph->max_row);
graph->node[graph->n].band_id = band_id;
- zero = isl_calloc_array(ctx, int, graph->n_edge + nvar);
+ zero = isl_calloc_array(ctx, int, graph->max_row);
graph->node[graph->n].zero = zero;
graph->n++;
if (graph_alloc(ctx, &graph, graph.n,
isl_union_map_n_map(validity) + isl_union_map_n_map(proximity)) < 0)
goto error;
+ if (compute_max_row(&graph, domain) < 0)
+ goto error;
graph.root = 1;
graph.n = 0;
if (isl_union_set_foreach_set(domain, &extract_node, &graph) < 0)
return schedule ? isl_space_get_ctx(schedule->dim) : NULL;
}
+/* Return an isl_union_map of the schedule. If we have already constructed
+ * a band forest, then this band forest may have been modified so we need
+ * to extract the isl_union_map from the forest rather than from
+ * the originally computed schedule.
+ */
__isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
{
int i;
if (!sched)
return NULL;
+ if (sched->band_forest)
+ return isl_band_list_get_suffix_schedule(sched->band_forest);
+
umap = isl_union_map_empty(isl_space_copy(sched->dim));
for (i = 0; i < sched->n; ++i) {
isl_multi_aff *ma;
isl_band *band;
unsigned start, end;
- band = isl_calloc_type(ctx, isl_band);
+ band = isl_band_alloc(ctx);
if (!band)
return NULL;
- band->ref = 1;
band->schedule = schedule;
band->parent = parent;
for (j = 0; j < band->n; ++j)
band->zero[j] = schedule->node[i].zero[start + j];
- band->map = isl_union_map_empty(isl_space_copy(schedule->dim));
+ band->pma = isl_union_pw_multi_aff_empty(isl_space_copy(schedule->dim));
for (i = 0; i < schedule->n; ++i) {
isl_multi_aff *ma;
- isl_map *map;
+ isl_pw_multi_aff *pma;
unsigned n_out;
if (!active[i])
continue;
ma = isl_multi_aff_copy(schedule->node[i].sched);
- map = isl_map_from_multi_aff(ma);
- n_out = isl_map_dim(map, isl_dim_out);
- map = isl_map_project_out(map, isl_dim_out, end, n_out - end);
- map = isl_map_project_out(map, isl_dim_out, 0, start);
- band->map = isl_union_map_union(band->map,
- isl_union_map_from_map(map));
+ n_out = isl_multi_aff_dim(ma, isl_dim_out);
+ ma = isl_multi_aff_drop_dims(ma, isl_dim_out, end, n_out - end);
+ ma = isl_multi_aff_drop_dims(ma, isl_dim_out, 0, start);
+ pma = isl_pw_multi_aff_from_multi_aff(ma);
+ band->pma = isl_union_pw_multi_aff_add_pw_multi_aff(band->pma,
+ pma);
}
- if (!band->map)
+ if (!band->pma)
goto error;
return band;
return isl_band_list_dup(schedule->band_forest);
}
+/* Call "fn" on each band in the schedule in depth-first post-order.
+ */
+int isl_schedule_foreach_band(__isl_keep isl_schedule *sched,
+ int (*fn)(__isl_keep isl_band *band, void *user), void *user)
+{
+ int r;
+ isl_band_list *forest;
+
+ if (!sched)
+ return -1;
+
+ forest = isl_schedule_get_band_forest(sched);
+ r = isl_band_list_foreach_band(forest, fn, user);
+ isl_band_list_free(forest);
+
+ return r;
+}
+
static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
__isl_keep isl_band_list *list);
isl_band_list *children;
p = isl_printer_start_line(p);
- p = isl_printer_print_union_map(p, band->map);
+ p = isl_printer_print_union_pw_multi_aff(p, band->pma);
p = isl_printer_end_line(p);
if (!isl_band_has_children(band))