Add comments and some debug code
@@ -2152,18 +2152,35 @@ int get_next_min_vertex_scc_cluster(int scc_id, PlutoProg *prog,
}
int min_scc_id = get_min_convex_successor(scc_id, prog);
+ if (min_scc_id == prog->ddg->num_sccs) {
+ /* There is no minimum convex successor */
+ for (int i = 0; i < max_dim; i++) {
+ if (colourable_dims[i]) {
+ free(colourable_dims);
+ IF_DEBUG(
+ printf(
+ "No convex successors. Returning vertex %d for colouring\n",
+ i););
+ return scc_offset + i;
+ }
+ }
+ }
int succ_dims;
bool *succ_colourable_dims = get_colourable_dims(
min_scc_id, prog, colour, &succ_dims, discarded_list, num_discarded);
+ /* Get the predecessors of the smallest convex successor */
unsigned num_preds;
int *pred_list = get_convex_preds_from_convex_successors(
min_scc_id, scc_id, convex_successors, num_convex_successors,
&num_preds);
+ /* Get common dims among the predecessors of the min scc */
common_dims =
get_common_dims(min_scc_id, pred_list, num_preds, succ_colourable_dims,
succ_dims, colour, current_colour, prog);
+
+ /* If there are no common dims then return the first colourable dimension */
if (common_dims == NULL) {
for (int i = 0; i < max_dim; i++) {
if (colourable_dims[i]) {
@@ -2173,6 +2190,9 @@ int get_next_min_vertex_scc_cluster(int scc_id, PlutoProg *prog,
}
}
}
+ /* This dimension dim of the SCC allows colouring of maximum number of
+ * predecessors. Find a corresponding dimension in the current scc that can
+ * be coloured with this dimension */
int dim = get_colouring_dim(common_dims, max_dim);
int fcg_vertex = sccs[min_scc_id].fcg_scc_offset + dim;
for (int i = 0; i < max_dim; i++) {
@@ -2185,6 +2205,7 @@ int get_next_min_vertex_scc_cluster(int scc_id, PlutoProg *prog,
return scc_offset + dim;
}
+ /* Normal brute force heuristic */
for (int i = 0; i < max_dim; i++) {
int v = scc_offset + i;
if (!is_discarded(v, discarded_list, num_discarded)) {
@@ -2821,6 +2842,7 @@ void find_permutable_dimensions_scc_based(int *colour, PlutoProg *prog) {
}
for (int i = 1; i <= max_colours; i++) {
+ IF_DEBUG(printf("Colouring FCG with colour %d\n", i););
for (int j = 0; j < prog->ddg->num_sccs; j++) {
prog->ddg->sccs[j].is_scc_coloured = false;
}
